题目描述
传送门
题目大意：一个凸n边形，N个顶点按照逆时针从0～n-l编号。随机站在凸多边形内的某个位置，标记为 P点。将P点与n个顶点各连一条边，形成N个三角形。求P点，0号点，1号点形成的三角形的面 积是N个三角形中最小的一个的概率。
题解
nlogn半平面交。 主要就是化简出解析式，然后用半平面交求解不等式组。 可以用叉积表示三角形的面积，注意别叉反了，要么三角形的面积就是负的了。 设P(x,y)，可以得到
(x−a[i].x,y−a[i].y)×(x−a[i+1].x,y−a[i+1].y)>(x−a[0].x,y−a[0].y)×(x−a[1].x,y−a[1].y)
(a[i].y−a[i+1].y)x+(a[i+1].x−a[i].x)∗y+a[i].x∗a[i+1].y−a[i].y∗a[i+1].x>(a[0].y−a[1].y)x+(a[1].x−a[0].x)∗y+a[0].x∗a[1].y−a[0].y∗a[1].x
移项得
(a[i].y−a[i+1].y−a[0].y+a[1].y)x+(a[i+1].x−a[i].x−a[1].x+a[0].x)y+a[i].x∗a[i+1].y−a[i].y∗a[i+1].x−a[0].x∗a[1].y+a[0].y∗a[1].x>0
设
a=(a[i].y−a[i+1].y−a[0].y+a[1].y),b=(a[i+1].x−a[i].x−a[1].x+a[0].x),c=a[i].x∗a[i+1].y−a[i].y∗a[i+1].x−a[0].x∗a[1].y+a[0].y∗a[1].x
那么方程就化简成了
ax+by+c>0
的形式。 我们要用一个向量表示这条解析式，并且让向量的左边表示
ax+by+c>0
的部分。 我们选择在向量上的两个点，如果b>0,选取的两个点p1,p2的横坐标递增；如果b<0，选取的两个点的横坐标递减。向量
v=p2−p1
然后直接做
O(nlogn)
的半平面交就可以了。 需要注意的的细节就是a=0,b=0,a=0且b=0，这些情况需要特判。
代码
using namespace std;
const double inf=
1e17;
int n,
m,cnt,head,tail;
struct data{
double
x,
y;
data(double X=
0,double Y=
0) {
x=X,
y=Y;
}
}
s[N],p1[
10],p[N],poly[N];
data operator +(data a,data b){
return data(a.
x+b.
x,a.
y+b.
y);}
data operator -(data a,data b){
return data(a.
x-b.
x,a.
y-b.
y);}
data operator
*(data a,double t){
return data(a.
x*t,a.
y*t);}
data operator /(data a,double t){
return data(a.
x/t,a.
y/t);}
struct line{
data p,v; double ang;
line(data a=data(),data b=data()){
p=a; v=b-a;
ang=
atan2(v.
y,v.
x);
}
}l[N],
q[N];
bool operator <(line a,line b){
return a.ang<b.ang;}
void calc(
int i,
int j,double &a,double &b,double &c)
{
a=
s[i].
y-
s[j].
y;
b=
s[j].
x-
s[i].
x;
c=
s[i].
x*s[j].
y-
s[i].
y*s[j].
x;
}
void init()
{
p1[
1]=data(inf,inf); p1[
2]=data(-inf,inf); p1[
3]=data(-inf,-inf); p1[
4]=data(inf,-inf);
l[++cnt]=line(p1[
1],p1[
2]);
l[++cnt]=line(p1[
2],p1[
3]);
l[++cnt]=line(p1[
3],p1[
4]);
l[++cnt]=line(p1[
4],p1[
1]);
}
double cross(data a,data b)
{
return a.
x*b.
y-a.
y*b.
x;
}
data glt(line a,line b)
{
data v=a.p-b.p;
double t=cross(b.v,v)/cross(a.v,b.v);
return a.p+a.v
*t;
}
int dcmp(double
x)
{
if (fabs(
x)<eps)
return 0;
return x>
0?
1:-
1;
}
bool Onleft(line a,data p)
{
return dcmp(cross(a.v,p-a.p))>=
0;
}
void halfpins()
{
sort(l+
1,l+cnt+
1);
q[1]=l[
1]; head=tail=
1;
for (
int i=
2;i<=cnt;i++) {
while (head<tail&&!Onleft(l[i],p[tail-
1])) tail--;
while (head<tail&&!Onleft(l[i],p[head])) head++;
q[++tail]=l[i];
if (fabs(cross(
q[tail].v,
q[tail-1].v))<
0) {
tail--;
if (Onleft(
q[tail],l[i].p))
q[tail]=l[i];
}
if (head<tail)p[tail-
1]=glt(
q[tail],
q[tail-1]);
}
while (head<tail&&!Onleft(
q[head],p[tail-
1])) tail--;
if (tail-head<=
1)
return;
p[tail]=glt(
q[tail],
q[head]);
for (
int i=head;i<=tail;i++)
poly[++
m]=p[i];
poly[
m+
1]=poly[
1];
}
double area(data a[],
int n)
{
double ans=
0;
for (
int i=
2;i<=n-
1;i++)
ans+=cross(a[i]-a[
1],a[i+
1]-a[
1]);
return ans;
}
int main()
{
freopen(
"a.in",
"r",stdin);
scanf(
"%d",&n);
for (
int i=
1;i<=n;i++) scanf(
"%lf%lf",&
s[i].
x,&
s[i].
y);
s[n+
1]=
s[
1];
double squ=area(
s,n);
for (
int i=
1;i<=n;i++) l[++cnt]=line(
s[i],
s[i+
1]);
double a,b,c; double a1,b1,c1; double a2,b2,c2;
calc(
1,
2,a1,b1,c1);
bool pd=true;
for (
int i=
2;i<=n;i++) {
calc(i,i+
1,a2,b2,c2);
a=a2-a1; b=b2-b1; c=c2-c1;
if (a==
0&&b==
0&&c<
0) {
pd=false;
break;
}
if (b==
0) {
double t=-c/a;
if (a>
0) l[++cnt]=line(data(t,
0),data(t,-
1));
else l[++cnt]=line(data(t,
0),data(t,
1));
continue;
}
if (a==
0) {
double t=-c/b;
if (b>
0) l[++cnt]=line(data(
0,t),data(
1,t));
else l[++cnt]=line(data(
0,t),data(-
1,t));
continue;
}
data p1,p2; p1.
x=
1; p2.
x=
2;
p1.
y=(-c-a
*p1.
x)/b;
p2.
y=(-c-a
*p2.
x)/b;
if (b<
0) swap(p1,p2);
l[++cnt]=line(p1,p2);
}
init();
halfpins();
if (!pd||
m==
0) {
printf(
"0.0000\n");
return 0;
}
double s1=area(poly,
m);
printf(
"%.4lf\n",s1/squ);
}
