QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#313254 | #7730. Convex Checker | QOJ114514ancestor | WA | 1ms | 7344kb | C++14 | 3.2kb | 2024-01-24 16:55:57 | 2024-01-24 16:55:57 |
Judging History
answer
#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
#define ld double
using namespace std;
const ld eps=1e-4;
ld sqr(ld x){return x*x;}
int sgn(ld x){return x>eps?1:(x<-eps?-1:0);}
struct point{
ld x,y;
point(int X=0,int Y=0){x=X,y=Y;}
point operator+(const point&a)const{return {x+a.x,y+a.y};}
point operator-(const point&a)const{return {x-a.x,y-a.y};}
point operator*(const ld a)const{return {x*a,y*a};}
point operator/(const ld a)const{
if(!a){cerr<<"point div 0";return {0,0};}
return {x/a,y/a};}
bool operator==(const point&a)const{
return !sgn(x-a.x)&&!sgn(y-a.y);}
point rotate(ld t)const{
/*???????? t*/
return {x*cos(t)-y*sin(t),x*sin(t)-y*cos(t)};}
point rot90()const{
/*???????? 90 ?*/
return {-y,x};}
point unit()const{
/*????????????*/
return *this/sqrt(sqr(x)+sqr(y));}
}O;
ld dis(const point&a,const point&b){
return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
struct line{
point s,t;
line(point S=point(0,0),point T=point(0,0)){s=S,t=T;}
};
ld dot(const point&a,const point&b){
/*??*/
return a.x*b.x+a.y*b.y;}
ld det(const point&a,const point&b){
/*?????????????*/
return a.x*b.y-b.x*a.y;}
bool turn_left(const point&a,const point&b,const point&c){
/*AB ?????? AC ??????? (0,pi) ???*/
return sgn(det(b-a,c-a))>0;}
bool parallel(const line&a,const line&b){
/*?? a,b ????*/
return !sgn(det(b.t-b.s,a.t-a.s));}
bool same_dir(const line&a,const line&b){
/*?? a,b ????*/
return parallel(a,b)&&sgn(dot(b.t-b.s,a.t-a.s))>0;}
bool point_on_segment(const point&a,const line&l){
/*? a ????? l ?*/
if(l.s==l.t)return a==l.s;
return !sgn(det(l.s-a,a-l.t))&&sgn(dot(l.s-a,a-l.t))<=0;}
bool two_side(const point&a,const point&b,const line&l){
/*? a,b ????? l ??*/
return sgn(det(a-l.s,l.t-l.s))*sgn(det(b-l.s,l.t-l.s))<0;}
bool inter_judge(const line&a,const line&b){
/*?? a,b ????*/
return point_on_segment(b.s,a)||point_on_segment(b.t,a)||
point_on_segment(a.s,b)||point_on_segment(a.t,b)||
two_side(a.s,a.t,b)&&two_side(b.s,b.t,a);}
point line_intersect(const line&a,const line&b){
/*??? a,b ???*/
ld u=det(a.t-a.s,b.s-a.s),v=-det(a.t-a.s,b.t-a.s);
return (b.s*v+b.t*u)/(v+u);}
bool ray_inter_judge(const line&a,const line&b){
/*?? a,b ????*/
if(parallel(a,b))return 0;
point p=line_intersect(a,b);line c={a.s,p},d={d.s,p};
return(point_on_segment(p,a)||point_on_segment(a.t,c))&&
(point_on_segment(p,b)||point_on_segment(b.t,d));}
ld point_to_line(const point&p,const line&l){
/*? p ??? l ??*/
return abs(det(l.t-l.s,p-l.s))/dis(l.s,l.t);}
ld point_to_segment(const point&p,const line&l){
/*? p ??? l ??*/
if(l.s==l.t||sgn(dot(l.s-p,l.t-l.s))*sgn(dot(l.t-p,l.t-l.s))>0)
return min(dis(p,l.s),dis(p,l.t));
return point_to_line(p,l);}
#define N 200005
int n;point p[N];ld ans;
ld get_angle(point a,point b,point c){
/*???? ACB*/
ld theta=atan2(a.x-c.x,a.y-c.y)-atan2(b.x-c.x,b.y-c.y);
if(sgn(theta)==-1)theta+=2*M_PI;
return theta;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cin>>n;
for(int i=0;i<n;i++)cin>>p[i].x>>p[i].y;
for(int i=0;i<n;i++){point a=p[i],b=p[(i+1)%n],c=p[(i+2)%n];
ld ag=get_angle(a,c,b);
// cout<<ag<<endl;
if(sgn(ag-M_PI)==1){
if(i==0)reverse(p,p+n),i=-1;
else cout<<"No",exit(0);
}
else ans+=ag;
}
if(!sgn(ans-(n-2)*M_PI))cout<<"Yes\n";
else cout<<"No\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7344kb
input:
3 0 0 1 0 0 1
output:
Yes
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 1ms
memory: 7128kb
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: 7280kb
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: 6996kb
input:
3 0 0 0 0 0 0
output:
No
result:
ok answer is NO
Test #5:
score: 0
Accepted
time: 1ms
memory: 7240kb
input:
5 1 0 4 1 0 1 2 0 3 2
output:
No
result:
ok answer is NO
Test #6:
score: -100
Wrong Answer
time: 0ms
memory: 7156kb
input:
5 0 0 1000000000 0 1000000000 500000000 1000000000 1000000000 0 1000000000
output:
Yes
result:
wrong answer expected NO, found YES