QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#313063 | #7730. Convex Checker | zjjws | WA | 1ms | 3780kb | C++14 | 5.5kb | 2024-01-24 15:49:11 | 2024-01-24 15:49:12 |
Judging History
answer
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define LL long long
using namespace std;
bool ifnum(char x){return x>='0'&&x<='9';}
bool ifupchr(char x){return x>='A'&&x<='Z';}
bool iflochr(char x){return x>='a'&&x<='z';}
struct Rin
{
char c;
char gc()
{
return getchar();
}
Rin&operator >>(int &x)
{
bool tag=false;x=0;
for(c=gc();c>'9'||c<'0';c=gc())if(c=='-'){c=gc();tag=true;break;}
for(;c>='0'&&c<='9';c=gc())x=(x<<1)+(x<<3)+(c^'0');if(tag)x=-x;return *this;
}
Rin&operator >>(LL &x)
{
bool tag=false;x=0;
for(c=gc();c>'9'||c<'0';c=gc())if(c=='-'){c=gc();tag=true;break;}
for(;c>='0'&&c<='9';c=gc())x=(x<<1)+(x<<3)+(c^'0');if(tag)x=-x;return *this;
}
Rin&operator >>(char &x)
{
for(c=gc();!ifnum(c)&&!iflochr(c)&&!ifupchr(c);c=gc());
x=c;
return *this;
}
Rin&operator >>(string &x)
{
x.clear();
for(c=gc();!ifnum(c)&&!iflochr(c)&&!ifupchr(c);c=gc());
for(;ifnum(c)||iflochr(c)||ifupchr(c);c=gc())x.push_back(c);
return *this;
}
}rin;
#define rin(x) rin>>x
void jh(int &x,int &y){if(x^y)x^=y^=x^=y;return;}
void jh(LL &x,LL &y){if(x^y)x^=y^=x^=y;return;}
int min(int x,int y){return x<y?x:y;}
int max(int x,int y){return x>y?x:y;}
LL min(LL x,LL y){return x<y?x:y;}
LL max(LL x,LL y){return x>y?x:y;}
const double eps=1e-10;
const double PI=acos(-1.0);
double sgn(double x){return (x>eps)-(x<-eps);}
struct PT
{
double x,y;
PT(){x=0;y=0;}
PT(double x,double y):x(x),y(y){}
PT operator -(const PT &a)const {return PT(x-a.x,y-a.y);}
PT operator +(const PT &a)const {return PT(x+a.x,y+a.y);}
PT operator *(const double a)const {return PT(x*a,y*a);}
friend PT operator *(const double &a,const PT &b){return PT(a*b.x,a*b.y);}
PT operator /(const double a)const {return PT(x/a,y/a);}
bool operator ==(const PT &a){return sgn(x-a.x)==0&&sgn(y-a.y)==0;}
bool operator !=(const PT &a){return !(*this==a);}
PT perp(){return PT(-y,x);}
double arg(){return atan2(y,x);}
double norm(){return sqrt(x*x+y*y);}
double norm2(){return x*x+y*y;}
PT truncate(double r)
{
double k=norm();
if(sgn(k)==0)return *this;
r/=k;
return PT(x*r,y*r);
}
};
struct Line
{
PT s,t;
Line(){s=PT(0,0),t=PT(0,0);}
Line(PT x,PT y):s(x),t(y){}
};
double dot(PT a,PT b){return a.x*b.x+a.y*b.y;}
double det(PT a,PT b){return a.x*b.y-a.y*b.x;}
int turn_l_or_r(Line l,PT x)
{
double v=det(l.t-l.s,x-l.s);
return sgn(v);//1 为左侧(逆时针)0 为线上
}
double Edis(PT a,PT b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
double Edis2(PT a,PT b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}
PT perp(PT a) { return PT(-a.y, a.x); }
PT rotatel90(PT a) { return PT(-a.y, a.x); }
PT rotater90(PT a) { return PT(a.y, -a.x); }
PT rotatel(PT a, double t) {return PT(a.x*cos(t)-a.y*sin(t),a.x*sin(t)+a.y*cos(t));}
PT rotater(PT a, double t) {return PT(a.x*cos(t)+a.y*sin(t),-a.x*sin(t)+a.y*cos(t));}
double SQ(double x){return x*x;}
double rad_to_deg(double r){return r*180.0/PI;}
double deg_to_rad(double r){return r*PI/180.0;}
double get_angle(PT a,PT b){return acos(max(-1.0,min(1.0,dot(a,b)/a.norm()/b.norm())));}
PT midPT(PT a,PT b){return PT((a.x+b.x)/2.0,(a.y+b.y)/2.0);}
int pt_in_convex_n(vector<PT>&p,PT &x)
{
int n=p.size()-1;
int ans=1;
for(int i=0;i<n;i++)
{
int s=turn_l_or_r(Line(p[i],p[i+1]),x);
ans=min(ans,s);
}
return ans;//1 为在内,0在边界,-1在外
}
double pt_dis_line(Line l,PT x)
{
if(l.s==l.t)return Edis(l.s,x);
return abs(det(l.t-l.s,x-l.s))/(l.t-l.s).norm();
}
double pt_dis_segment(PT &a,PT &b,PT &x)
{
double ans=min(Edis(a,x),Edis(b,x));
double v1=dot(b-a,x-a),v2=dot(b-a,b-a);
if(sgn(v2-v1)>=0&&sgn(v1)>=0)ans=min(ans,abs(det(b-a,x-a))/(b-a).norm());
return ans;
}
double pt_dis_convex(vector<PT>&p,PT &x)
{
int n=p.size()-1;
double ans=pt_dis_segment(p[0],p[1],x);
for(int i=1;i<n;i++)ans=min(ans,pt_dis_segment(p[i],p[i+1],x));
return ans;
}
const int N=2e5+3;
int n;
vector<PT>p;
vector<PT>convex_hull(vector<PT> a)
{
if(a.size()<=2)return a;
sort(a.begin(),a.end(),[&](PT u,PT v){return u.x==v.x?u.y<v.y:u.x<v.x;});
PT stand=p[0];
sort(a.begin(),a.end(),[&](PT u,PT v){
int s=sgn(det(u-stand,v-stand));//1 为v在u左侧
return s!=0?s>0:Edis(u,stand)<Edis(v,stand);
});
vector<PT>ret;ret.clear();
for(auto i:a)
{
for(;ret.size()>1&&turn_l_or_r(Line(ret[ret.size()-2],ret[ret.size()-1]),i)==-1;)ret.pop_back();
ret.push_back(i);
}
return ret;
}
int t;
int d[N];
int main()
{
rin>>n;
// p.reserve(n);
for(int i=0;i<n;i++)
{
int x,y;rin>>x>>y;
// p[i]=PT(x,y);
p.push_back(PT(x,y));
}
sort(p.begin(),p.end(),[&](PT a,PT b){return a.x==b.x?a.y<b.y:a.x<b.x;});
for(int i=0,j;i<n;i=j+1)
{
for(j=i;j+1<n&&p[j+1]==p[j];j++);
if(j!=i){puts("No");return 0;}
// pp.push_back(p[i]);
}
vector<PT> convex=convex_hull(p);
// for(auto i:convex)printf("(%.2lf,%.2lf) ",i.x,i.y);
if(convex.size()!=n)puts("No");
else puts("Yes");
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3740kb
input:
3 0 0 1 0 0 1
output:
Yes
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 0ms
memory: 3736kb
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: 3592kb
input:
4 0 0 0 3 1 2 1 1
output:
Yes
result:
ok answer is YES
Test #4:
score: 0
Accepted
time: 1ms
memory: 3780kb
input:
3 0 0 0 0 0 0
output:
No
result:
ok answer is NO
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3608kb
input:
5 1 0 4 1 0 1 2 0 3 2
output:
Yes
result:
wrong answer expected NO, found YES