QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#493 | #279251 | #7730. Convex Checker | PhantomThreshold | PhantomThreshold | Success! | 2023-12-08 14:40:38 | 2023-12-08 14:40:39 |
Details
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 | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#279251 | #7730. Convex Checker | PhantomThreshold | WA | 53ms | 13296kb | C++20 | 2.2kb | 2023-12-08 14:40:20 | 2023-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";
}