卧薪尝胆,厚积薄发。
SCOI2015 小凸想跑步
Date: Sun Dec 02 22:00:40 CST 2018 In Category: NoCategory

Description:

给一个凸多边形,求选一个点向所有顶点连边和 $1-2$ 这条边组成的面积是最小的的概率。
$1\leqslant n\leqslant 10^5$

Solution:

发现每一个限制都可以化成一个半平面,也就是说对于两条线 $0-1$ 和 $i-i+1$ ,和这两条线组成的三角形面积相等的点在一条直线上,这条直线的一边是合法的,所以把这些拿出来做半平面交即可。

Code:


#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<cstring>
using namespace std;
int n;
#define MAXN 200010
struct point
{
double x,y;
}p[MAXN];
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 k){return (vector){a.x * k,a.y * k};}
double cross(vector a,vector b){return a.x * b.y - a.y * b.x;}
double angle(vector k){return atan2(k.y,k.x);}
struct plane
{
point p;vector v;
}pl[MAXN],q[MAXN];
bool equal(double a,double b){return fabs(a - b) <= 1e-6;}
int sign(double k){return (equal(k,0.0) ? 0 : (k < 0 ? -1 : 1));}
bool in(point p,plane k){return sign(cross(p - k.p,k.v)) >= 0;}
point intersection(plane a,plane b){return b.p + b.v * (cross(a.v,a.p - b.p) / cross(a.v,b.v));}
point middle(point a,point b,double f,double g)
{
return (point){(a.x * f + b.x * g) / (f + g),(a.y * f + b.y * g) / (f + g)};
}
bool cmp(plane a,plane b){return angle(a.v) < angle(b.v);}
double len(vector a){return sqrt(a.x * a.x + a.y * a.y);}
int ptr = 0;
int head,tail;
double dis(point a,point b){return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));}
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;++i)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
}
p[n + 1] = p[1];
double area = 0.0;
for(int i = 1;i <= n;++i)
{
area += cross(p[i],p[i + 1]);
}
double ans = 0;
for(int i = 2;i <= n;++i)
{
if(cross(p[2] - p[1],p[i + 1] - p[i]) == 0)
{
point a = middle(p[2],p[i],dis(p[1],p[2]),dis(p[i + 1],p[i]));
point b = middle(p[1],p[i + 1],dis(p[1],p[2]),dis(p[i + 1],p[i]));
if(sign(cross(p[i] - b,a - b)) >= 0)pl[++ptr] = (plane){a,b - a};
else pl[++ptr] = (plane){a,a - b};
}
else
{
point x = intersection((plane){p[2],p[2] - p[1]},(plane){p[i],p[i + 1] - p[i]});
vector a = middle(p[2],p[1],1,1) - x,b = middle(p[i + 1],p[i],1,1) - x;
double l;
l = len(a);a.x /= l;a.y /= l;
l = len(b);b.x /= l;b.y /= l;
a = a * dis(p[1],p[2]);
b = b * dis(p[i + 1],p[i]);
if(sign(cross(a,b)) < 0)pl[++ptr] = (plane){x,a * -1.0 + b * -1.0};
else pl[++ptr] = (plane){x,a + b};
}
}
for(int i = 1;i <= n;++i)
{
pl[++ptr] = (plane){p[i],p[i] - p[i + 1]};
}
sort(pl + 1,pl + 1 + ptr,cmp);
int tot = 0;
for(int i = 1;i <= ptr;++i)
{
if(tot == 0)pl[++tot] = pl[i];
else if(!equal(angle(pl[tot].v),angle(pl[i].v)))pl[++tot] = pl[i];
else if(!in(pl[tot].p,pl[i]))pl[tot] = pl[i];
}
head = 1;tail = 2;
q[1] = pl[1];q[2] = pl[2];
for(int i = 3;i <= tot;++i)
{
while(head < tail && !in(intersection(q[tail],q[tail - 1]),pl[i]))--tail;
while(head < tail && !in(intersection(q[head],q[head + 1]),pl[i]))++head;
q[++tail] = pl[i];
}
while(head < tail && !in(intersection(q[tail],q[tail - 1]),q[head]))--tail;
int m = tail - head + 1;
if(m <= 2)puts("0.0000");
else
{
for(int i = 1;i < m;++i)p[i] = intersection(q[head + i - 1],q[head + i]);
p[0] = p[m] = intersection(q[head],q[tail]);
for(int i = 0;i < m;++i)
{
ans += cross(p[i],p[i + 1]);
}
printf("%.4lf\n",ans / area);
}
return 0;
}
Copyright © 2020 wjh15101051
ღゝ◡╹)ノ♡