QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#333840 | #7730. Convex Checker | skywang60305 | WA | 0ms | 3808kb | C++14 | 1.7kb | 2024-02-20 17:47:22 | 2024-02-20 17:47:23 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
struct Point{
long long x,y;
Point(){}
Point(long long x,long long y):x(x),y(y){}
Point operator+(Point B){
return Point(x+B.x,y+B.y);
}
Point operator-(Point B){
return Point(x-B.x,y-B.y);
}
bool operator==(Point B){
return x-B.x==0 && y-B.y==0;
}
bool operator<(Point B){
return x-B.x<0|| (x-B.x==0 && y-B.y<0);
}
long long operator*(Point B){
return x*B.y-y*B.x;
}
};
typedef Point Vector;
typedef vector<Point> Points;
typedef Points Polygon;
Polygon Convex_hull(Points S){
int n=S.size();
if (n==1){
return S;
}
if (n==2){
if (S[0]==S[1]){
return {S[0]};
} else {
return S;
}
}
Polygon T(2*n);
sort(S.begin(),S.end());
int cur=-1;
for (int i=0;i<n;i++){
while (cur>0 && (T[cur]-T[cur-1])*(S[i]-T[cur-1])<=0){
cur--;
}
T[++cur]=S[i];
}
int pre=cur;
for (int i=n-2;i>=0;i--){
while (cur>0 && (T[cur]-T[cur-1])*(S[i]-T[cur-1])<=0){
cur--;
}
T[++cur]=S[i];
}
T.resize(cur);
return T;
}
int main(){
int n;
cin>>n;
Points S(n),Tmp(n);
for (int i=0;i<n;i++){
cin>>S[i].x>>S[i].y;
}
Tmp=S;
sort(Tmp.begin(),Tmp.end());
Tmp.erase(unique(Tmp.begin(),Tmp.end()),Tmp.end());
if (Tmp.size()!=n){
cout<<"No";
return 0;
}
Polygon T=Convex_hull(Tmp);
if (T.size()!=S.size()){
cout<<"No";
return 0;
}
for (int i=0;i<n;i++){
if (S[i]==T[0]){
bool flag1=true;
for (int j=1;j<n;j++){
if (!(S[(i+j)%n]==T[j])){
flag1=false;
break;
}
}
bool flag2=true;
for (int j=1;j<n;j++){
if (!(S[(i+j)%n]==T[n-j])){
flag2=false;
break;
}
}
puts(flag1 ||flag2 ? "Yes":"No");
return 0;
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3508kb
input:
3 0 0 1 0 0 1
output:
Yes
result:
ok answer is YES
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3808kb
input:
4 0 0 0 1 1 1 1 0
output:
No
result:
wrong answer expected YES, found NO