Submission #2914710


Source Code Expand

#include<bits/stdc++.h>

const int N = 10;

const double eps = 1e-9;
const double PI = acos(-1.0);
const double INF = 1e100;

inline int sig(double p){
    return (p > eps) - (p < -eps);
}

inline double sqr(double p){return p * p;}

class P{
public:
    double x, y;
    explicit P (double x = 0, double y = 0): x(x), y(y){}
    P operator + (const P &p)const{return P (x + p.x, y + p.y);}
    P operator - (const P &p)const{return P (x - p.x, y - p.y);}
    P operator * (const double &p)const{return P (x * p, y * p);}
    friend P operator * (const double &d, const P &p){return P (d * p.x, d * p.y);}
    P operator / (const double &p)const{return P (x / p, y / p);}
    double operator ^ (const P &p)const{return x * p.y - y * p.x;}
    double operator % (const P &p)const{return x * p.x + y * p.y;}
    double abs2()const{return *this % *this;}
    double abs()const{return std::sqrt(abs2());}
    double angle()const{
        double ret = std::atan2(y, x);
        if (ret < 0){
            ret += 2 * PI;
        }
        return ret;
    }

    // 逆时针旋转 rad 弧度
    P rot(const double &rad)const{
        double sin = std::sin(rad), cos = std::cos(rad);
        return P (x * cos - y * sin, x * sin + y * cos);
    }

    P rot90()const{
        return P (-y, x);
    }

    bool operator < (const P &p)const{
        if (sig(x - p.x)) return x < p.x;
        return y < p.y;
    }

    bool operator == (const P &p)const{
        return !sig(x - p.x) && !sig(y - p.y);
    }

    void read(){
        scanf("%lf%lf", &x, &y);
    }
};

class L{
public:
    P p, v;
    double angle;

    L (){}
    L (P a, P b):p(a), v(b - a){angle = std::atan2(v.y, v.x);}

    bool operator < (const L &l)const{
        return angle < l.angle;
    }

    P point(double t){
        return p + v * t;
    }
};

P proj(L l, P p){
    return l.p + l.v * (l.v % (p - l.p) / l.v.abs2());
}

P symmetry(L l, P p){
    P q = proj(l, p);
    return 2 * q - p;
}

void cross(double &l1, double &r1, double &l2, double &r2, double angle1, double angle2){
    if (angle1 < 0){
        r1 = std::min(r1, angle2);
        l1 = std::max(l1, angle1 + 2 * PI);
    }
    else{
        l1 = std::max(l1, angle1);
        r1 = std::min(r1, angle2);
        l2 = std::max(l2, angle1);
        r2 = std::min(r2, angle2);
    }
}

int n;
P s;
P p[N], q[N];
bool vis[N];
int cnt;

void dfs(int now, int n, std::vector <P> vec, double l1, double r1, double l2, double r2){
    if (now == n){
        ++ cnt;
        return;
    }
    for (int i = 1; i <= n; ++ i){
        if (vis[i]) continue;
        vis[i] = true;
        P p1 = vec[i], p2 = vec[i % n + 1];
        double angle1 = (p1 - s).angle(), angle2 = (p2 - s).angle();
        L l(p1, p2);
        if (angle1 > angle2){
            std::swap(angle1, angle2);
        }
        if (angle2 - angle1 > PI){
            angle2 -= 2 * PI;
            std::swap(angle1, angle2);
        }
        double tmpl1 = l1, tmpr1 = r1, tmpl2 = l2, tmpr2 = r2;
        cross(tmpl1, tmpr1, tmpl2, tmpr2, angle1, angle2);
        if (sig(tmpr1 - tmpl1) <= 0 && sig(tmpr2 - tmpl2) <= 0){
            vis[i] = false;
            continue;
        }
        std::vector <P> nvec = vec;
        for (int j = 1; j <= n; ++ j){
            nvec[j] = symmetry(l, nvec[j]);
        }
        dfs(now + 1, n, nvec, tmpl1, tmpr1, tmpl2, tmpr2);
        vis[i] = false;
    }
}

void solve(){
    s.read();
    for (int i = 1; i <= n; ++ i){
        p[i].read();
    }
    cnt = 0;
    memset(vis, 0, sizeof(vis));
    std::vector <P> vec(n + 1);
    for (int i = 1; i <= n; ++ i){
        vec[i] = p[i];
    }
    dfs(0, n, vec, 0, 2 * PI, 0, 2 * PI);
    printf("%d\n", cnt);
}

int main(){
    while (scanf("%d", &n), n){
        solve();
    }
    return 0;
}

/*
4
0 0
-10 -10
10 -10
10 10
-10 10
0
*/

Submission Info

Submission Time
Task E - Putter
User zhongzihao
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3996 Byte
Status WA
Exec Time 23 ms
Memory 640 KB

Compile Error

./Main.cpp: In member function ‘void P::read()’:
./Main.cpp:56:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lf%lf", &x, &y);
                                ^
./Main.cpp: In function ‘int main()’:
./Main.cpp:154:5: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     while (scanf("%d", &n), n){
     ^

Judge Result

Set Name all
Score / Max Score 0 / 100
Status
WA × 1
Set Name Test Cases
all Merged
Case Name Status Exec Time Memory
Merged WA 23 ms 640 KB