QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#278252#7906. Almost ConvexJacka1TL 1ms4800kbC++173.8kb2023-12-07 14:15:562023-12-07 14:15:56

Judging History

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

  • [2023-12-07 14:15:56]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:4800kb
  • [2023-12-07 14:15:56]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> PII;

const int N=4010;
int n;
namespace Geometry{
	const double pi=acos(-1);
	const double eps=1e-12;
	
	struct Point{//点坐标
		double x,y;
		int flag;
		Point(double x=0,double y=0):x(x),y(y) {}
		//可用Point a(1,2);语句直接将值设置为x=1,y=2
		//如果未设定初值则直接设置为x=0,y=0
		bool operator==(const Point a) const{
			return (fabs(x-a.x)<=eps&&fabs(y-a.y)<=eps);
		}
		bool operator<(const Point &b) const{//以横纵坐标从小到大排序
			return x == b.x ? y < b.y : x < b.x;
		}
	};
	typedef Point Vector;//向量
	
	//简化向量运算
	Vector operator +(Vector A,Vector B){
		return Vector(A.x+B.x,A.y+B.y);
	}
	Vector operator -(Vector A,Vector B){
		return Vector(A.x-B.x,A.y-B.y);
	}
	Vector operator *(Vector A,double p){
		return Vector(A.x*p,A.y*p);
	}
	Vector operator /(Vector A,double p){
		return Vector(A.x/p,A.y/p);
	}
	int sign(double x){//符号函数:精度为eps
		if(fabs(x)<eps) return 0;//x为0
		if(x<0) return -1;//x为负数
		return 1;//x为正数
	}
	
	int cmp(double x,double y){//比较函数:精度为eps
		if(fabs(x-y)<eps) return 0;//x与y相等
		if(x<y) return -1;//x小于y
		return 1;//x大于y
	}
	
	double cross(Point a,Point b){//向量叉积
		return a.x*b.y-b.x*a.y;
	}
	
	double area(Point a,Point b,Point c){//A为顶点,向量AB与向量AC的叉积,即三角形ABC面积的2倍(有向)
		return cross(b-a,c-a);
	}
	
	int stk[N];
	Point q[N];
	bool used[N];
	int top;
	void andrew(){//求凸包
		sort(q,q+n);//以横纵坐标从小到大排序
		for(int i=0;i<n;i++)
		{
			while(top>=2&&sign(area(q[stk[top-1]],q[stk[top]],q[i]))<=0)//
				//不带等号:可以求出所有点都在一条直线上的情况
			{
				if(sign(area(q[stk[top-1]],q[stk[top]],q[i]))<0)
					used[stk[top--]]=false;
				else top--;
			}
			stk[++top]=i;
			used[i]=true;
		}
		used[0]=false;
		for(int i=n-1;i>=0;i--)
		{
			if(used[i]) continue;
			while(top>=2&&sign(area(q[stk[top-1]],q[stk[top]],q[i]))<=0)//
				top--;
			stk[++top]=i;
		}
		//凸包上的点为1~top-1,q[top]与q[1]为同一点
		//该遍历为逆时针顺序!!!
		//      for (int i = 1; i <= top; i ++ )
		//          cout << stk[i] << ' ';
		//      cout<<endl;
	}
	
	
	int cnt;
	struct Line{//存储凸包上每条线段的起点和终点
		Point st,ed;
		double ang;
		int flag;
	}line[N];
	Point pg[N],ans[N];
	int l[N];
	
	double line_get_angle(const Line& a){
		return atan2(a.ed.y-a.st.y,a.ed.x-a.st.x);
	}
	
	bool line_cmp(const Line& a, const Line& b){
		double A=line_get_angle(a),B=line_get_angle(b);
		if (!cmp(A,B)) return area(a.st,a.ed,b.ed)<0;
		return A<B;
	}
}
using namespace Geometry;

void solve()//求半平面交
{
	scanf("%d",&n);
	for(int i=0;i<n;i++) 
	{
		scanf("%lf%lf",&q[i].x,&q[i].y);//读入凸包上的所有点
		q[i].flag=0;
	}
	andrew();
	for(int i=1;i<=top;i++) q[stk[i]].flag=1;//flag==1在凸包上
	
//	for(int i=1;i<=top;i++) cout<<q[stk[i]].x<<" "<<q[stk[i]].y<<endl;
	
	int ans=0;
	for(int i=0;i<n;i++)
	{
		if(q[i].flag) continue;
//		cout<<q[i].x<<" "<<q[i].y<<endl;
		int cnt=0,res=0;
		for(int j=0;j<n;j++)
		{
			if(i==j) continue;
			line[cnt++]={q[i],q[j]};
			if(q[j].flag) line[cnt-1].flag=1;
			else line[cnt-1].flag=0;
		}
		sort(line,line+cnt,line_cmp);
		line[cnt++]=line[0];
//		for(int j=0;j<cnt;j++) cout<<line[j].ed.x<<" "<<line[j].ed.y<<" "<<line[j].flag<<endl;
		for(int j=1;j<cnt;j++)
		{
			if(line[j].flag&&line[j-1].flag) res++;
		}
		ans+=res;
//		cout<<res<<endl;
	}
	printf("%d",ans+1);
}

int main()
{
	int t = 1;
	//cin>>t;
	while(t--) solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 1ms
memory: 4792kb

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: 1ms
memory: 4432kb

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 1ms
memory: 4700kb

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: 4484kb

input:

4
0 0
0 3
3 0
3 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: -100
Time Limit Exceeded

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: