QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#243447 | #7730. Convex Checker | tnos# | WA | 0ms | 3924kb | C++14 | 1.9kb | 2023-11-08 11:54:43 | 2023-11-08 11:54:45 |
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 11:54:43]
- 提交
answer
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-9;
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);
}
void print()
{
printf("%.2f %.2f\n",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 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;
int main()
{
int n,i;
vec x;
double ans=0;
scanf("%d",&n);
set<pair<int,int>> tp;
for(i=1;i<=n;i++)
{
int xx,y;
scanf("%d%d",&xx,&y);
tp.insert({xx,y});
x.x=xx,x.y=y,t.insert(x);
}
if(tp.size()<n)
{
puts("No");
return 0;
}
t.build();
if(t.cnt<n)
puts("No");
else
puts("Yes");
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3924kb
input:
3 0 0 1 0 0 1
output:
Yes
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 0ms
memory: 3704kb
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: 3636kb
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: 3672kb
input:
3 0 0 0 0 0 0
output:
No
result:
ok answer is NO
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3920kb
input:
5 1 0 4 1 0 1 2 0 3 2
output:
Yes
result:
wrong answer expected NO, found YES