QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#331010 | #7730. Convex Checker | Hanghang | WA | 0ms | 3688kb | C++14 | 974b | 2024-02-17 22:09:54 | 2024-02-17 22:09:54 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dcmp(ll x){return x>0?1:x<0?-1:0;}
struct Point{ll x,y;};
typedef Point Vec;
Vec operator +(Vec a,Vec b){return {a.x+b.x,a.y+b.y};}
Vec operator -(Vec a,Vec b){return {a.x-b.x,a.y-b.y};}
bool operator <(Vec a,Vec b){return a.x!=b.x?a.x<b.x:a.y<b.y;}
ll Cro(Vec a,Vec b){return a.x*b.y-a.y*b.x;}
ll Dot(Vec a,Vec b){return a.x*b.x+a.y*b.y;}
bool PolyShape(Point *p,int n)
{
if(Cro(p[2]-p[1],p[3]-p[1])<0)reverse(p+1,p+n+1);
int mn=1;Point Q[n+3];
for(int i=1;i<=n;i++)if(p[i]<p[mn])mn=i;
for(int i=1;i<=n;i++)Q[i]=i+mn-1<=n?p[i+mn-1]:p[i+mn-1-n];
Q[n+1]=Q[1];Q[n+2]=Q[2];
for(int i=2;i<n;i++)if(dcmp(Cro(p[i]-p[1],p[i+1]-p[i]))<=0)return 0;
for(int i=1;i<=n;i++)if(dcmp(Cro(p[i+1]-p[i],p[i+2]-p[i+1]))<=0)return 0;
return 1;
}
const int N=1e6+3;
int n;
Point p[N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>p[i].x>>p[i].y;
puts(PolyShape(p,n)?"Yes":"No");
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3688kb
input:
3 0 0 1 0 0 1
output:
No
result:
wrong answer expected YES, found NO