QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#313254#7730. Convex CheckerQOJ114514ancestorWA 1ms7344kbC++143.2kb2024-01-24 16:55:572024-01-24 16:55:57

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 19:27:17]
  • hack成功,自动添加数据
  • (/hack/727)
  • [2024-07-04 19:17:30]
  • hack成功,自动添加数据
  • (/hack/726)
  • [2024-01-24 16:55:57]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7344kb
  • [2024-01-24 16:55:57]
  • 提交

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