QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#341028 | #7730. Convex Checker | crsfaa# | WA | 1ms | 3640kb | C++14 | 1.3kb | 2024-02-29 15:05:51 | 2024-02-29 15:05:53 |
Judging History
answer
#include<bits/stdc++.h>
#define Yukinoshita namespace
#define Yukino std
using Yukinoshita Yukino;
int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9') w=ch=='-'?-1:1,ch=getchar();
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
const int mxn=2e5+5;
using ll=long long;
struct vec
{
int x,y;
friend bool operator <(const vec &x,const vec &y)
{
return x.x==y.x?x.y<y.y:x.x<y.x;
}
friend ll operator *(const vec &x,const vec &y)
{
return 1ll*x.x*y.y-1ll*x.y*y.x;
}
friend vec operator -(const vec &x,const vec &y)
{
return vec({x.x-y.x,x.y-y.y});
}
}a[mxn],b[mxn];
ll check(vec a,vec b,vec c)
{
return (b-a)*(c-a);
}
double dis(vec a,vec b)
{
return sqrt(1ll*(a.x-b.x)*(a.x-b.x)+1ll*(a.y-b.y)*(a.y-b.y));
}
int main()
{
int n=read(),i,top=0;
for(i=1;i<=n;i++)
a[i].x=read(),a[i].y=read();
sort(a+1,a+1+n);
ll sum=0;
for(i=2;i<n;i++)
sum+=abs(check(a[1],a[i],a[i+1]));
for(i=1;i<=n;i++)
{
for(;top>1&&check(b[top-1],b[top],a[i])<=0;top--);
b[++top]=a[i];
}
int tp=top;
for(i=n-1;i;i--)
{
for(;top>tp&&check(b[top-1],b[top],a[i])<=0;top--);
b[++top]=a[i];
}
for(i=2;i<n;i++)
sum-=abs(check(b[1],b[i],b[i+1]));
if(top==n&&!sum) cout<<"Yes";
else cout<<"No";
// printf("%.8f",s);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3640kb
input:
3 0 0 1 0 0 1
output:
No
result:
wrong answer expected YES, found NO