QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#493#279251#7730. Convex CheckerPhantomThresholdPhantomThresholdSuccess!2023-12-08 14:40:382023-12-08 14:40:39

詳細信息

Extra Test:

Wrong Answer
time: 0ms
memory: 3820kb

input:

3
0 0
1000000000 1000000000
-1000000000 -999999999

output:

No

result:

wrong answer expected YES, found NO

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#279251#7730. Convex CheckerPhantomThresholdWA 53ms13296kbC++202.2kb2023-12-08 14:40:202023-12-08 14:40:54

answer

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const long double PI = acos(-1);
struct Point{
    ll x,y;
};
using Vec = Point;
struct Line{
    Point P;Vec v;
};
struct Seg{
    Point A,B;
};
int sgn(ll x){
    if(x == 0)return 0;
    if(x > 0)return 1;
    return -1;
}
Vec operator + (const Vec &A,const Vec &B){
    return {A.x + B.x,A.y + B.y};
}
Vec operator - (const Vec &A,const Vec &B){
    return {A.x - B.x,A.y - B.y};
}
ll operator * (const Vec &A,const Vec &B){
    return A.x * B.x + A.y * B.y;
}
ll operator ^ (const Vec &A,const Vec &B){
    return A.x * B.y - A.y * B.x;
}
long double len(Vec x){
    return sqrt(1.0 * x.x * x.x + 1.0 * x.y * x.y);
}
long double cos_t(Vec u,Vec v){
    return 1.0 * (u * v) / len(u) / len(v);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<Point> a(n);
    map<pair<int,int>,int> mp;
    for(int i = 0;i < n;i ++){
        cin >> a[i].x >> a[i].y;
        if(mp.find({a[i].x,a[i].y}) != mp.end()){
            cout << "No\n";
            return 0;
        }
        mp[{a[i].x,a[i].y}] = 1;
    }
    int flag = sgn((a[1] - a[0]) ^ (a[2] - a[1]));
    if(flag == 0){
        cout << "No\n";
        return 0;
    }
    for(int i = 1;i < n;i ++){
        auto nxt = [&](int x){
            return (x + 1) % n;
        };
        int nxt1 = nxt(i),nxt2 = nxt(nxt1);
        int pd = sgn((a[nxt1] - a[i]) ^ (a[nxt2] - a[nxt1]));
        if(pd != flag){
            cout << "No\n";
            return 0;
        }
    }
    long double sum = 0;
    for(int i = 0;i < n;i ++){
        auto nxt = [&](int x){
            return (x + 1) % n;
        };
        auto pre = [&](int x){
            return (x - 1 + n) % n;
        };
        int pr = pre(i),nx = nxt(i);
        Vec v1 = a[pr] - a[i],v2 = a[nx] - a[i];
//        if((v1 * v2) <= 0){
//            cout << "No\n";return 0;
//        }
        long double co = cos_t(v1,v2);
        long double ang = acos(co);
        sum += ang;
    }
    long double Ang = 1.0 * (n - 2) * PI;
    cerr << Ang << " " << sum << "\n";
    if(fabs(Ang - sum) <= 1e-4){
        cout << "Yes\n";
    }
    else cout << "No\n";
}