QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#455013#7906. Almost ConvexsunkaihuanRE 0ms3884kbC++148.0kb2024-06-25 17:40:042024-06-25 17:40:04

Judging History

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

  • [2024-06-25 17:40:04]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3884kb
  • [2024-06-25 17:40:04]
  • 提交

answer

#include<bits/stdc++.h>
#define ld double
#define PI 3.14159265358
using namespace std;
const ld eps=1e-8;
ld sqr(ld x){return x*x;}
int sgn(ld x){return x>eps?1:(x<-eps?-1:0);}
struct point{
	ld x,y;int c;
	point(ld X=0,ld 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);}
	bool operator<(const point&a)const{
		return x<a.x||x==a.x&&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_line(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))==0);}
bool point_on_segment(const point&a,const line&l){
	/*点 a 是否在线段 l 上*/
	return point_on_line(a,l)&&(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 ist(i) while(c.size()>f&&!turn_left(*prev(c.end()),*prev(prev(c.end())),a[i]))c.pop_back();c.push_back(a[i]);
vector<point> Andrew(vector<point>a){
	/*极角序求点集 a 的凸包*/
	if(a.size()<=2)return a;
	stable_sort(a.begin(),a.end());
	vector<point> c;int f=1;for(int i=0;i<(int)a.size();i++){ist(i)}
	f=c.size();for(int i=(int)a.size()-2;i>=0;i--){ist(i)}
	c.pop_back();
	return c;
}
ld area(vector<point>&a){
	/*求简单多边形 a 的面积*/
	ld ret=0;
	for(int i=0;i<a.size();i++)
		ret+=det(a[i],a[(i+1)%a.size()]);
	return abs(ret/2);
}
bool inside(point p,vector<point>&a){
	/*判断点 p 是否在凸包 a 内部*/
	for(int i=0;i<a.size();i++)
		if(!turn_left(a[i],a[(i+1)%a.size()],p))return 0;
	return 1;
}
bool inter_judge2(const line&a,const line&b){
return point_on_segment(a.t,b)||two_side(a.s,a.t,b)&&two_side(b.s,b.t,a);}

point p[505];vector<point> w,id;
bool v[505];int n,m,ans=1;
vector<int> ok[505];
int t[505][505][2],nx[505][505][2];

int ccc[505][505];
int calc(int i,int j,int k){
	if(i>j)swap(i,j);if(i>k)swap(i,k);if(j>k)swap(j,k);
	//cerr<<p[i].x<<" "<<p[i].y<<" "<<p[j].x<<" "<<p[j].y<<" "<<p[k].x<<" "<<p[k].y<<"\n";
	// //cerr<<i<<" "<<j<<" "<<k<<"\n";
	if(p[i].x==p[j].x)return abs(ccc[i][j]+ccc[j][k]+ccc[k][i]-2);
	if(p[j].x==p[k].x)return abs(ccc[i][j]+ccc[j][k]+ccc[k][i]-1);
	return abs(ccc[i][j]+ccc[j][k]+ccc[k][i])-turn_left(p[i],p[k],p[j]);
}

int main(){
    // freopen("in.in","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0); 
	cin>>n;
	for(int i=1;i<=n;i++)cin>>p[i].x>>p[i].y;stable_sort(p+1,p+n+1);
	for(int i=1;i<=n;i++)p[i].c=i,w.push_back(p[i]);id=Andrew(w);m=id.size();
    // if(n==500)for(int i=1;i<=70;i++)cout<<p[i].x<<" "<<p[i].y<<" ";
	for(auto j:id)v[j.c]=1;//cerr<<1;
	for(int i=1;i<=n;i++){//cerr<<i<<"\n";
		for(int j=i+1;j<=n;j++){
			for(int k=1;k<=n;k++)
				ccc[i][j]+=inter_judge2(line(p[i],p[j]),line(p[k],point(p[k].x,1000000)));
			ccc[j][i]=-ccc[i][j];
		}
	}
	// if(n==500)for(int i=0;i<m;i++)cout<<id[i].c<<" "<<id[i].x<<" "<<id[i].y<<"\n";
	for(int i=1;i<=n;i++){if(v[i])continue;//cerr<<i<<":\n";
		for(int j=0;j<m;j++){
			if(calc(i,id[j].c,id[(j+1)%m].c)==0)ok[i].push_back(j),ans++;
			//if(calc(i,id[j].c,id[(j+1)%m].c)==1)ans+=2;
		}//cerr<<'\n';
		cerr<<ans<<'\n';
	}line t1,t2;int pl,x;point px;//cerr<<2;
	// for(int i=1;i<=n;i++){
	// 	if(v[i])continue;//cerr<<i<<": ";
	// 	for(auto j:ok[i])//cerr<<j<<" ";//cerr<<'\n';
	cerr<<ans<<"\n";//if(n==500)while(1);
	// for(int i=1;i<=n;i++){
	// 	if(v[i])continue;
	// 	pl=0;x=ok[i].size();if(x==0)continue;
	// 	for(int j=0;j<m;j++){
	// 		t[i][j][0]=pl;
	// 		if(j==ok[i][pl])pl=(pl+1)%x;
	// 		//cerr<<t[i][j][0]<<" "; 
	// 	}//cerr<<"\n";
	// }for(int i=1;i<=n;i++){
	// 	if(v[i])continue;
	// 	x=ok[i].size();pl=x-1;if(x==0)continue;
	// 	for(int j=m-1;j>=0;j--){
	// 		t[i][j][1]=pl;
	// 		if(j==ok[i][pl])pl=(pl+x-1)%x;
	// 		//cerr<<t[i][j][1]<<" ";
	// 	}//cerr<<"\n";
	// }//cerr<<3;if(n==500)cout<<m<<"\n";
	// for(int i=1;i<=n;i++){if(v[i])continue;
	// 	for(int j=1;j<=n;j++){if(v[j]||i==j)continue;
	// 		for(int k=0;k<m;k++){
    //             if(parallel({p[i],p[j]},{id[k],id[(k+1)%m]}))continue;
	// 			px=line_intersect({p[i],p[j]},{id[k],id[(k+1)%m]});//cerr<<i<<" "<<j<<" "<<px.x<<" "<<px.y<<"\n";
	// 			if(abs(px.x-p[i].x)>=abs(px.x-p[j].x)&&abs(px.y-p[i].y)>=abs(px.y-p[j].y)&&point_on_segment(px,{id[k],id[(k+1)%m]}))
	// 				{nx[i][j][0]=(k+1)%m;break;}
	// 		}for(int k=m-1;k>=0;k--){
    //             if(parallel({p[i],p[j]},{id[k],id[(k+1)%m]}))continue;
	// 			px=line_intersect({p[i],p[j]},{id[k],id[(k+1)%m]});//cerr<<i<<" "<<j<<" "<<px.x<<" "<<px.y<<"\n";
	// 			if(abs(px.x-p[i].x)>=abs(px.x-p[j].x)&&abs(px.y-p[i].y)>=abs(px.y-p[j].y)&&point_on_segment(px,{id[k],id[(k+1)%m]}))
	// 				{nx[i][j][1]=(k+m-1)%m;break;}
	// 		}//cerr<<nx[i][j][0]<<" "<<nx[i][j][1]<<"\n";
	// 	}
	// }//if(n==500)for(int i=126;i<=250;i++){cout<<ok[i].size()<<" ";if(i%125==0)cout<<'\n';}
    // for(int i=1;i<=n;i++){if(v[i]||(!ok[i].size()))continue;
	// 	for(int j=i+1;j<=n;j++){if(v[j]||i==j||(!ok[j].size()))continue;x=ok[j].size();
	// 		for(int k=0;k<m;k++)
	// 			if(calc(i,id[k].c,id[k+1].c)==0&&calc(i,j,id[(k+1)%m].c)==0&&calc(j,id[k].c,id[(k+1)%m].c)==0)ans++;
	// 		cerr<<ans<<"\n";
	// 		for(auto k:ok[i]){
	// 			t1={p[j],id[(k+1)%m]},t2={p[i],id[k]};
	// 			if(inter_judge(t1,t2))
	// 				ans+=(t[j][(k+m-1)%m][1]-t[j][nx[j][i][0]][0]+x+1)%x;
	// 			else{
	// 				t1={p[j],id[k]},t2={p[i],id[(k+1)%m]};
	// 				if(inter_judge(t1,t2))
	// 					ans+=(t[j][nx[j][i][1]][1]-t[j][(k+1)%m][0]+x+1)%x;
	// 				else ans+=x;
	// 			}cerr<<ans<<"\n";
	// 		}
	// 	}
	// }
    cout<<ans; 
    // for(int i=1;i<=n;i++)
    //     for(int j=i+1;j<=n;j++)
    //         for(int k=j+1;k<=n;k++)
                //cerr<<i<<' '<<j<<' '<<k<<' '<<calc(i,j,k)<<'\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3884kb

input:

7
1 4
4 0
2 3
3 1
3 5
0 0
2 4

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3768kb

input:

5
4 0
0 0
2 1
3 3
3 1

output:

5

result:

ok 1 number(s): "5"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3776kb

input:

6
0 0
3 0
3 2
0 2
1 1
2 1

output:

7

result:

ok 1 number(s): "7"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

4
0 0
0 3
3 0
3 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: -100
Runtime Error

input:

2000
86166 617851
383354 -277127
844986 386868
-577988 453392
-341125 -386775
-543914 -210860
-429613 606701
-343534 893727
841399 339305
446761 -327040
-218558 -907983
787284 361823
950395 287044
-351577 -843823
-198755 138512
-306560 -483261
-487474 -857400
885637 -240518
-297576 603522
-748283 33...

output:


result: