题目大意:
题解:
设点坐标,利用叉积可以解出当p坐标为\((x_p,y_p)\)时,与边i--(i+1)构成的三角形面积为
\[(y_i - y_{i+1})x_p+(x_{i+1} - x_i)y_p+(x_iy_{i+1}-x_{i+1}y_i)
\]
\]
我们又知道三角形\(0 -- 1 -- (p)\)是最小的,所以我们列出不等式后移项变号得
\[(y_0-y_1-y_i+y_{i+1})x_p+(x_1-x_0-x_{i+1}+x_i)y_p+(x_0y_1-x_1y_0-x_iy_{i+1}+x_{i+1}y_i) < 0
\]
\]
我们发现这是一个\(ax^2 + bx + c < 0\)的形式
所以我们就可以使用数学上的线性规划来解决问题
当然在OI里就可以写半平面交了
不要忘记还应限制这个点在多边形中.
Code
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
const int maxn = 110010;
const double eps = 1e-9;
inline int dcmp(const double &x){
if(x < eps && x > -eps) return 0;
return x > 0 ? 1 : -1;
}
struct Point{
double x,y;
Point(){}
Point(const double &a,const double &b){
x=a;y=b;
}
};
typedef Point Vector;
Vector operator + (const Vector &a,const Vector &b){
return Vector(a.x+b.x,a.y+b.y);
}
Vector operator - (const Vector &a,const Vector &b){
return Vector(a.x-b.x,a.y-b.y);
}
Vector operator * (const Vector &a,const double &b){
return Vector(a.x*b,a.y*b);
}
double cross(const Vector &a,const Vector &b){
return a.x*b.y - a.y*b.x;
}
struct line{
Point p;
Vector v;
double alpha;
line(){}
line(const Point &a,const Point &b){
p = a;v = b;
alpha = atan2(v.y,v.x);
}
};
inline bool cmp(const line &a,const line &b){
return a.alpha < b.alpha;
}
inline Point lineInterion(const line &l1,const line &l2){
Vector u = l1.p - l2.p;
double t = cross(l2.v,u)/cross(l1.v,l2.v);
return l1.p + l1.v*t;
}
inline bool onLeft(const Point &p,const line &l){
return dcmp(cross(l.v,p-l.p)) > 0;
}
line lines[maxn<<2],q[maxn<<2];
Point p[maxn<<2];int l,r;
inline bool halfInterion(int n){
sort(lines+1,lines+n+1,cmp);
l = r = 1;q[1] = lines[1];
for(int i=2;i<=n;++i){
while(l < r && !onLeft(p[r-1],lines[i])) -- r;
while(l < r && !onLeft(p[l],lines[i]) ) ++ l;
if(dcmp(cross(q[r].v,lines[i].v)) == 0)
q[r] = onLeft(q[r].p,lines[i]) ? q[r] : lines[i];
else q[++r] = lines[i];
if(l < r) p[r-1] = lineInterion(q[r],q[r-1]);
}
while(l < r && !onLeft(p[r-1],q[l])) -- r;
return (r-l) > 1;
}
double x[maxn],y[maxn];
int main(){
int n;read(n);
int cnt = 0;
double total = .0;
for(int i=0;i<n;++i){
scanf("%lf%lf",&x[i],&y[i]);
}x[n] = x[0];y[n] = y[0];
for(int i=0;i<n;++i){
lines[++cnt] = line(Point(x[i],y[i]),Vector(x[i+1]-x[i],y[i+1]-y[i]));
}
for(int i=1;i<n-1;++i){
total += abs(cross(Point(x[i]-x[0],y[i]-y[0]),Point(x[i+1]-x[0],y[i+1]-y[0])));
}
for(int i=1;i<n;++i){
double a = y[0] - y[1] - y[i] + y[i+1];
double b = x[1] - x[0] - x[i+1] + x[i];
double c = x[0]*y[1] - x[1]*y[0] - x[i]*y[i+1] + x[i+1]*y[i];
Point p,v(-b,a);
if(dcmp(b) == 0) p = Point(-c/a,0.0);
else p = Point(0.0,-c/b);
lines[++cnt] = line(p,v);
}
bool flag = halfInterion(cnt);
if(!flag) return puts("0.000");
double ans = .0;p[r] = lineInterion(q[l],q[r]);
for(int i=l+1;i<r;++i){
ans += abs(cross(p[i]-p[l],p[i+1]-p[l]));
}
printf("%.4lf\n",ans/total);
getchar();getchar();
return 0;
}