题目链接：
https://jzoj.net/senior/#contest/show/2686/2
题目：
题解：
说实话这题调试差不多花了我十小时，不过总算借着这道题大概了解了计算几何的基础知识
首先，若$1$号星与其他两颗星共线，那么显然新出现的 1 号星也必须在这条线上，因此可行的面积为 0 ，下文我们考虑 1 号星不与其他任意两颗星共线的情况
一个$O(n^2 log n)$的做法是枚举每一对星，$1$号星移动必然不能越过每一对星形成的直线，这样我们就可以通过半平面交解决这个问题
事实上，在这$O(n^2)$条直线中很多是冗余的，我们考虑只选出可能产生贡献的
1.考虑半平面$p_2-p_3,p_4-p_3,...,p_n-p_2$
2.令与星$p_i$极角相差不超过 $π$，且极角相差最大的星为 $p_j$ ，考虑半平面 $p_i−p_j$
然后运行半平面交即可
显然策略$1$是成立的，策略$2$画画图就很显然了
若$p_j$与$p_i$之间还有点$p_z$，那么显然$p_i-p_z$会被$p_i-p_j$遮挡掉，因为我们是要绕着原点的
特别需要注意的是我们每次添加直线要确保原点在所有直线左侧(或者在所有直线的右侧也可以，代码是左侧)
代码：
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cstdio>
#define il inline
using namespace std;
typedef double db; const int N=1e6+;
const db pi=acos(-1.0);
const db eps=1e-;
int n,cnt;
il int dcmp(db x) {return fabs(x)<eps?:x<?-:;}
struct point
{
db x,y;db ang;
point (db _x=,db _y=):x(_x),y(_y) {ang=atan2(y,x);}
}p[N];
bool operator < (point a,point b) {return dcmp(a.ang-b.ang)<;}
point operator + (point a,point b) {return (point){a.x+b.x,a.y+b.y};}
point operator - (point a,point b) {return (point){a.x-b.x,a.y-b.y};}
point operator * (db t,point a) {return (point){a.x*t,a.y*t};}
db det(point a,point b) {return a.x*b.y-a.y*b.x;}
struct seg
{
int a,b;db ang;
seg(int _a=,int _b=):a(_a),b(_b) {ang=atan2(p[b].y-p[a].y,p[b].x-p[a].x);};
}l[N];
bool segleft(seg x,seg y)
{
point u=p[x.b]-p[x.a];
point v=p[y.b]-p[y.a];
db tp=det(u,v);
return (tp>)||((tp==)&&det(u,p[y.a]-p[x.a])>);
}
bool operator < (seg x,seg y)
{
db o=x.ang-y.ang;
if (!dcmp(o)) return segleft(y,x);
return dcmp(o)<;
}
inline int read()
{
char ch=getchar();int s=,f=;
while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}
return s*f;
}
point inter(seg x,seg y)//x与y的交点
{
point u=p[x.b]-p[x.a];
point v=p[y.b]-p[y.a];
point w=p[x.a]-p[y.a];
db d=det(w,v)/det(v,u);
return p[x.a]+d*u;
}
bool pright(seg x,point y)//点y是不是在直线x的右侧
{
point a=p[x.b]-p[x.a];
point b=y-p[x.a];
return dcmp(det(a,b))<=;
}
void add(int x,int y)//确保原点在左侧
{
if (pright(seg(x,y),point(,))) l[++cnt]=seg(y,x);
else l[++cnt]=seg(x,y);
}
int qu[N];
point a[N];
void work()
{
sort(l+,l++cnt);
int he=,ta=;
qu[++ta]=;
for (int i=;i<=cnt;i++)
if (dcmp(l[i].ang-l[i-].ang))
{
while (he<ta&&pright(l[i],inter(l[qu[ta]],l[qu[ta-]]))) --ta;
while (he<ta&&pright(l[i],inter(l[qu[he]],l[qu[he+]]))) ++he;
qu[++ta]=i;
}
while (he<ta&&pright(l[qu[he]],inter(l[qu[ta]],l[qu[ta-]]))) --ta;
if (ta-he<=)
{
puts("0.000000000");
return;
}
int tp=;
qu[he-]=qu[ta];
for (int i=he;i<=ta;i++) a[++tp]=inter(l[qu[i]],l[qu[i-]]);
a[tp+]=a[];
db res=;
for (int i=;i<=tp;i++) res+=det(a[i],a[i+]);
printf("%.10lf\n",res*0.5);
}
int main()
{
freopen("everdream.in","r",stdin);
freopen("everdream.out","w",stdout);
int NUM=read(),T=read();
while (T--)
{
n=read()-;
p[].x=1.0*read();p[].y=1.0*read();
for (int i=;i<=n;i++) p[i].x=1.0*read()-p[].x,p[i].y=1.0*read()-p[].y,p[i].ang=atan2(p[i].y,p[i].x);
cnt=;
sort(p+,p++n);
for (int i=;i<=n;i++) p[n+i]=p[i],p[n+i].ang+=*pi;
bool flag=;
for (int i=;i<=n;i++)
{
if (!dcmp(p[i].ang-p[i+].ang)) {flag=;break;}
add(i,i%n+);
point ty=(point){,};ty.ang=p[i].ang+pi;
int t=lower_bound(p+,p++*n,ty)-p;
if (t!=i+n&&!dcmp(p[t].ang-p[i].ang-pi)) {flag=;break;}
--t;
if (i!=t&&i+n!=t) add(i,(t-)%n+);
}
if (flag) {puts("0.000000000");continue;}
p[n+]=(point){-1e6,-1e6};p[n+]=(point){1e6,-1e6};
p[n+]=(point){1e6,1e6};p[n+]=(point){-1e6,1e6};
p[n+]=p[n+]-p[];p[n+]=p[n+]-p[];
p[n+]=p[n+]-p[];p[n+]=p[n+]-p[];
add(n+,n+);add(n+,n+);
add(n+,n+);add(n+,n+);
work();
}
return ;
}