QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#243450 | #7730. Convex Checker | tnos# | WA | 0ms | 3936kb | C++14 | 2.1kb | 2023-11-08 12:01:52 | 2023-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-12-08 14:40:48]
- hack成功,自动添加数据
- (//qoj.ac/hack/493)
- [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