Description

给出平面上n个点，其中1号点是可以移动的，但是移动的范围不能改变任意三个点所成的角的状态（$[0,\pi ),[\pi ,\pi ],(\pi ,2\pi ]$）。
求可移动的范围。

$n\le 500000$

Solution

画一个图可以感受出来，实际上1号点移动的范围就是不能越过其他点的任意一对点的连线。

这样有一个很直观的做法就是枚举两个点，加入它们连线向1号点方向的半平面，然后做个半平面交即可，时间复杂度是$O(n^2\log n)$的
这显然不能接受。

我们将所有的点按照极角序排序，可以发现实际上真正有用的半平面是非常有限的。
观察到只有极角序相邻的点的连线，以及每个点关于1号点的对称点 的极角序相邻的两个点与这个点的连线是有用的

显然这些半平面的个数是$O(n)$的，做个半平面交就好了。
时间复杂度$O(n\log n)$

Code

#include <bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
#define N 600005
using namespace std;

map<int,bool> h[N]; 
namespace geometry
{
    
	const double eps=1e-10;
	const double pi=acos(-1);
	struct node
	{
    	
		double x,y;
		node(double _x=0,double _y=0){
    x=_x,y=_y;}
	};
	node operator +(node x,node y) {
    return node(x.x+y.x,x.y+y.y);}
	node operator -(node x,node y) {
    return node(x.x-y.x,x.y-y.y);}
	node operator *(double x,node y) {
    return node(x*y.x,x*y.y);}
	double crs(node x,node y) {
    return x.x*y.y-x.y*y.x;}
	double ang(node x) 
	{
    
		double v=atan2(x.y,x.x);
		if(v<0) v+=2*pi;
		return v;
	}

	struct line
	{
    
		node p,v;
		line(){
    };
		line(node _p,node _v) {
    p=_p,v=_v;}
	};
	node dot(line x,line y) {
    return y.p+(crs(x.v,x.p-y.p)/crs(x.v,y.v))*y.v;}
	bool inside(line x,node y)
	{
    
		return (crs(x.v,y-x.p)>eps);
	}
	bool in(line x,node y)
	{
    
		return abs(crs(x.v,y-x.p)<=eps);
	}
}
using namespace geometry;

int t,n,n1,n2;
node a[N],ab[N];
line d[4*N],db[4*N];
struct px
{
    
	double v;
	int p;
	friend bool operator <(px x,px y) {
    return x.v<y.v;}
}u2[N];


int pre(int x) {
    return (x==2)?n:x-1;}
int suf(int x) {
    return (x==n)?2:x+1;}

bool cmp2(px x,px y)
{
    
	return(x.v+eps<y.v||(abs(x.v-y.v)<=eps&&inside(d[y.p],d[x.p].p)));
}
double get()
{
    
	fo(i,1,n1) 
	{
    
		if(in(d[i],node(0,0))) return 0;
		u2[i]=(px){
    ang(d[i].v),i};
		db[i]=d[i];
	}
	static int dq[4*N],d2[4*N];
	n2=0;
	sort(u2+1,u2+n1+1,cmp2);

	fo(i,1,n1) d[i]=db[u2[i].p];
	
	fo(i,1,n1) if(i==1||fabs(ang(d[i].v)-ang(d[i-1].v))>eps) d2[++n2]=i;
	int l=1,r=2;dq[1]=d2[1],dq[2]=d2[2];
	fo(i1,3,n2)
	{
    
		int i=d2[i1];
		while(l<r&&!inside(d[i],dot(d[dq[r]],d[dq[r-1]]))) r--;
		while(l<r&&!inside(d[i],dot(d[dq[l]],d[dq[l+1]]))) l++;
		dq[++r]=i;
	}
	while(l+2<r&&!inside(d[dq[l]],dot(d[dq[r]],d[dq[r-1]]))) r--;
	double s=0;
	fo(i,l,r-2) s+=crs(dot(d[dq[i]],d[dq[i+1]]),dot(d[dq[i+1]],d[dq[i+2]]));
	s+=crs(dot(d[dq[r-1]],d[dq[r]]),dot(d[dq[r]],d[dq[l]]));
	s+=crs(dot(d[dq[r]],d[dq[l]]),dot(d[dq[l]],d[dq[l+1]]));
	return s/2;
}


int main()
{
    
	freopen("everdream.in","r",stdin);
	freopen("everdream.out","w",stdout);
	int tp;
	cin>>tp;
	cin>>t;
	int cnt=0;
	while(t--)
	{
    
		scanf("%d",&n);
		n1=0;
		fo(i,1,n) h[i].clear();
		fo(i,1,n) 
		{
    
			int x,y;
			scanf("%d%d",&x,&y);
			a[i]=(i==1)?node(x,y):node(x,y)-a[1];
			ab[i]=a[i];
			u2[i]=(px){
    ang(a[i]),i};
		}
		//a[++n]=node(1e6,-1e6),a[++n]=node(1e6,1e6),a[++n]=node(-1e6,1e6),a[++n]=node(-1e6,-1e6);
		sort(u2+2,u2+n+1);
		fo(i,2,n) a[i]=ab[u2[i].p];
		for(int i=2,j=3;i<=n;i++)
		{
    
			node w=(-1)*a[i];
			while(crs(a[j],w)>0) j=suf(j);
			if(pre(j)!=i&&!h[i][pre(j)]) 
			{
    
				h[i][pre(j)]=h[pre(j)][i]=1;
				line w=line(a[i],a[pre(j)]-a[i]);
				d[++n1]=(inside(w,node(0,0)))?w:line(a[pre(j)],a[i]-a[pre(j)]);
			}
			if(j!=i&&!h[i][j]) 
			{
    
				h[i][j]=h[j][i]=1;
				line w=line(a[j],a[i]-a[j]);
				d[++n1]=(inside(w,node(0,0)))?w:line(a[i],a[j]-a[i]);
			}
			if(j==i+1) j=suf(j);

			if(!h[i][suf(i)])
			{
    
				h[i][suf(i)]=h[suf(i)][i]=1;
				line w1=line(a[i],a[suf(i)]-a[i]);
				d[++n1]=(inside(w1,node(0,0)))?w1:line(a[suf(i)],a[i]-a[suf(i)]);
			}
		}
		
		d[++n1]=line(node(1e6,-1e6)-a[1],node(0,1e6));//右边界
		d[++n1]=line(node(1e6,1e6)-a[1],node(-1e6,0));//上边界
		d[++n1]=line(node(-1e6,1e6)-a[1],node(0,-1e6));//左边界
		d[++n1]=line(node(-1e6,-1e6)-a[1],node(1e6,0));//下边界


		printf("%.10lf\n",get());		
	}
}