QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#243450#7730. Convex Checkertnos#WA 0ms3936kbC++142.1kb2023-11-08 12:01:522023-11-08 12:01:53

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 19:27:17]
  • hack成功,自动添加数据
  • (/hack/727)
  • [2024-07-04 19:17:30]
  • hack成功,自动添加数据
  • (/hack/726)
  • [2023-11-08 12:01:53]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3936kb
  • [2023-11-08 12:01:52]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define double long long
struct vec
{
	double x,y;
	vec(){}
	vec(double x_,double y_)
	{
		x=x_,y=y_;
	}
	friend vec operator +(const vec &x,const vec &y)
	{
		return vec(x.x+y.x,x.y+y.y);
	}
	friend vec operator -(const vec &x,const vec &y)
	{
		return vec(x.x-y.x,x.y-y.y);
	}
	friend vec operator *(const vec &x,const double &y)
	{
		return vec(x.x*y,x.y*y);
	}
	friend double operator &(const vec &x,const vec &y)
	{
		return x.x*y.x+x.y*y.y;
	}
	friend double operator *(const vec &x,const vec &y)
	{
		return x.x*y.y-x.y*y.x;
	}
	double mol()
	{
		return sqrt(x*x+y*y);
	}
	friend bool operator <(const vec &x,const vec &y)
	{
		return x.x==y.x?x.y<y.y:x.x<y.x;
	}
	friend double check(vec a,vec b,vec c)
	{
	    return (b-a)*(c-a);
	}
	friend double dis(const vec &x,const vec &y)
	{
		return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
	}
};
struct convex_hull
{
	int n,cnt;
	vector<vec> a,s;
	convex_hull()
	{
		a.push_back({});
	}
	void insert(vec x)
	{
		a.push_back({});
		a[++n]=x;
	}
	void build()
	{
		int i,t;
//		sort(a.begin()+1,a.begin()+1+n);
		s.push_back({});
		s[0]=a[1];
		for(i=2;i<=n;i++)
		{
			while(cnt&&check(s[cnt-1],s[cnt],a[i])<0)
				cnt--,s.pop_back();
			s.push_back({});
			s[++cnt]=a[i];
		}
		t=cnt;
		for(i=n-1;i>=1;i--)
		{
			while(cnt!=t&&check(s[cnt-1],s[cnt],a[i])<0)
				cnt--,s.pop_back();
			s.push_back({});
			s[++cnt]=a[i];	
		}
	}
}t,t2;
int x[200005],y[200005];
int main()
{
	int n,i,j,w;
	vec xxx;
	double ans=0;
	scanf("%d",&n);
	set<pair<int,int>> tp;
	for(i=1;i<=n;i++)
		scanf("%d%d",&x[i],&y[i]),tp.insert({x[i],y[i]});
	if(tp.size()<n)
	{
		puts("No");
		return 0;
	}
	pair<int,int> mn{2e9,0};
	for(i=1;i<=n;i++)
		mn=min(mn,{x[i],y[i]});
	for(i=1;i<=n;i++)
		if(make_pair(x[i],y[i])==mn)
		{
			for(j=0,w=i;j<n;j++,w=w%n+1)
				xxx.x=x[w],xxx.y=y[w],t.insert(xxx);
			for(j=0,w=i;j<n;j++,w=w==1?n:w-1)
				xxx.x=x[w],xxx.y=y[w],t2.insert(xxx);
			break;
		}
	t.build();
	if(t.cnt==n||t2.cnt==n)
		puts("Yes");
	else
		puts("No");	
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3612kb

input:

3
0 0
1 0
0 1

output:

Yes

result:

ok answer is YES

Test #2:

score: 0
Accepted
time: 0ms
memory: 3936kb

input:

4
0 0
0 1
1 1
1 0

output:

Yes

result:

ok answer is YES

Test #3:

score: 0
Accepted
time: 0ms
memory: 3680kb

input:

4
0 0
0 3
1 2
1 1

output:

Yes

result:

ok answer is YES

Test #4:

score: 0
Accepted
time: 0ms
memory: 3684kb

input:

3
0 0
0 0
0 0

output:

No

result:

ok answer is NO

Test #5:

score: 0
Accepted
time: 0ms
memory: 3676kb

input:

5
1 0
4 1
0 1
2 0
3 2

output:

No

result:

ok answer is NO

Test #6:

score: -100
Wrong Answer
time: 0ms
memory: 3620kb

input:

5
0 0
1000000000 0
1000000000 500000000
1000000000 1000000000
0 1000000000

output:

Yes

result:

wrong answer expected NO, found YES