QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#342141 | #7730. Convex Checker | xyz123 | WA | 1ms | 3920kb | C++14 | 1.6kb | 2024-03-01 09:12:44 | 2024-03-01 09:12:45 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
long long a,cn;
long double eps=1e-9,an;
struct p{long double q,w;}l[1000001],m[1000001],st[1000001],g[1000001];
bool cmp(p qq,p ww){if(qq.q==ww.q) return qq.w<ww.w;return qq.q<ww.q;}
p del(p qq,p ww){return p{qq.q-ww.q,qq.w-ww.w};}
long double cross(p qq,p ww){return qq.q*ww.w-qq.w*ww.q;}
bool cmp1(p qq,p ww)
{
return cross(del(qq,l[1]),del(ww,l[1]))<0;
}
bool ch(p qq,p ww,p ee)
{
if(fabs(cross(del(qq,ww),del(ee,ww)))<eps)
{
printf("No");
exit(0);
}
return cross(del(qq,ww),del(ee,ww))>0;
}
long double get(p qq,p ww){return sqrt((qq.q-ww.q)*(qq.q-ww.q)+(qq.w-ww.w)*(qq.w-ww.w));}
int main()
{
scanf("%lld",&a);
for(int i=1;i<=a;i++) scanf("%Lf%Lf",&l[i].q,&l[i].w),g[i]=l[i];
sort(g+1,g+a+1,cmp);
for(int i=1;i<a;i++)
{
if(fabs(g[i].q-g[i+1].q)<eps&&fabs(g[i].w-g[i+1].w)<eps)
{
printf("No");
return 0;
}
}
long long tt=0;
for(int i=1;i<=a;i++)
{
if(fabs(g[1].q-l[i].q)<eps&&fabs(g[1].w-l[i].w)<eps)
{
tt=i;break;
}
}
for(int i=tt;i<=a;i++) g[i-tt+1]=l[i];
for(int i=1;i<tt;i++) g[a-tt+1+i]=l[i];
for(int i=1;i<=a;i++) l[i]=g[i];
for(int i=2;i<=a;i++) m[++cn]=l[i];
for(int i=1;i+1<=cn;i++)
{
if(fabs(cross(del(m[i],l[1]),del(m[i+1],l[1])))<eps)
{
printf("No");
return 0;
}
}
if(ch(m[1],l[1],m[2]))
{
for(int i=1;i<=cn/2;i++) swap(m[i],m[cn-i+1]);
}
cn=0;
st[++cn]=l[1];
m[a]=l[1];
for(int i=1;i<=a;i++)
{
while(cn>1&&ch(st[cn],st[cn-1],m[i]))
{
printf("No");
return 0;
}
st[++cn]=m[i];
}
printf("Yes");
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3920kb
input:
3 0 0 1 0 0 1
output:
Yes
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 1ms
memory: 3864kb
input:
4 0 0 0 1 1 1 1 0
output:
Yes
result:
ok answer is YES
Test #3:
score: 0
Accepted
time: 1ms
memory: 3912kb
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: 3788kb
input:
3 0 0 0 0 0 0
output:
No
result:
ok answer is NO
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 3888kb
input:
5 1 0 4 1 0 1 2 0 3 2
output:
Yes
result:
wrong answer expected NO, found YES