QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#333840#7730. Convex Checkerskywang60305WA 0ms3808kbC++141.7kb2024-02-20 17:47:222024-02-20 17:47:23

Judging History

This is the latest submission verdict.

  • [2024-07-04 19:27:17]
  • hack成功,自动添加数据
  • (/hack/727)
  • [2024-07-04 19:17:30]
  • hack成功,自动添加数据
  • (/hack/726)
  • [2024-02-20 17:47:23]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3808kb
  • [2024-02-20 17:47:22]
  • Submitted

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