题解
半平面交
题目要求求出让(Delta PP_0P_1)在所有形成的三角形中面积最小
那么可以考虑对于点(P(x , y) , P_{i} , P_{i + 1})
一定有$ (x - x_1 , y - y_1) imes (x_0 - x_1 , y_0 - y_1) < (x_{i+1} - x_i , y_{i + 1} - y_i) imes (x - x_i , y - y_i)(
那么把式子化开就可以得到若干)Ax + By + C > 0(这样的不等式
)(y_1 + y_i - y_0 - y_{i + 1})x + (x_0 + x_{i + 1} - x_1 - x_i) + P_i imes P_{i + 1} - P_0 imes P_1 > 0$
然后就可以上半平面交了
注意一下线段的方向
说一下如何判断线段的方向:
分情况讨论:
如果(B)不为(0)
如果(B>0)那么就让线段的方向为从左指右
否则就让线段的方向为从右指左
如果(B=0)
那么就说明ta斜率是无限大
那就判断如果(A>0),就让线段的方向为从上指下
反之就是从下指上
代码
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
const int M = 200005 ;
const double EPS = 1e-10 ;
const double INF = 1e18 ;
using namespace std ;
inline int read() {
char c = getchar() ; int x = 0 , w = 1 ;
while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }
while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }
return x*w ;
}
double tot , ans ;
int n , cnt , head , tail ;
inline int sgn(double x) {
if(fabs(x) < EPS) return 0 ;
return x > 0 ? 1 : -1 ;
}
struct Vec {
double x , y ;
Vec (double Tx = 0 , double Ty = 0) {
x = Tx , y = Ty ;
}
} pi[M] , p[M] ;
inline Vec operator + (Vec A , Vec B) {
return Vec (A.x + B.x , A.y + B.y) ;
}
inline Vec operator - (Vec A , Vec B) {
return Vec (A.x - B.x , A.y - B.y) ;
}
inline Vec operator * (Vec A , double B) {
return Vec (A.x * B , A.y * B) ;
}
inline Vec operator / (Vec A , double B) {
return Vec (A.x / B , A.y / B) ;
}
struct Line {
Vec s , v , t ; double Ang ;
Line () { } ;
Line (Vec A , Vec B) {
s = A , t = B ;
v = t - s ; Ang = atan2(v.y , v.x) ;
}
} l[M] , que[M] ;
inline double Dot(Vec A , Vec B) {
return A.x * B.x + A.y * B.y ;
}
inline double Cross(Vec A , Vec B) {
return A.x * B.y - A.y * B.x ;
}
inline Vec GLI(Line a , Line b) {
Vec c = b.s - a.s ;
double t = Cross(b.v , c) / Cross(b.v , a.v) ;
return a.s + a.v * t ;
}
inline bool OnRight(Vec P , Line L) {
return ( sgn(Cross(P - L.s , L.v)) > 0 && sgn(Cross(P - L.t , L.v)) > 0 ) ;
}
inline bool operator < (Line A , Line B) {
if(fabs(A.Ang - B.Ang) > EPS) return A.Ang < B.Ang ;
else return OnRight(B.s , A) ;
}
inline double f(double x , double A , double B , double C) {
return ( - A * x - C) / B ;
}
inline void SI() {
sort(l + 1 , l + cnt + 1) ;
head = 1 , tail = 1 ; que[1] = l[1] ;
for(int i = 2 ; i <= cnt ; i ++) {
while(head < tail && OnRight(p[tail - 1] , l[i])) -- tail ;
while(head < tail && OnRight(p[head] , l[i])) ++ head ;
if(sgn(que[tail].Ang - l[i].Ang) == 0) continue ;
que[++tail] = l[i] ;
if(head < tail) p[tail - 1] = GLI(que[tail] , que[tail - 1]) ;
}
while(head < tail && OnRight(p[tail - 1] , que[head])) -- tail ;
while(head < tail && OnRight(p[head] , que[tail])) ++ head ;
p[tail] = GLI(que[head] , que[tail]) ;
}
int main() {
n = read() ;
for(int i = 0 ; i < n ; i ++) pi[i].x = read() , pi[i].y = read() ;
pi[n] = pi[0] ;
for(int i = 0 ; i < n ; i ++)
l[++cnt] = Line (pi[i] , pi[i + 1]) ;
for(int i = 0 ; i < n ; i ++)
tot += Cross(pi[i] , pi[i + 1]) ;
for(int i = 1 ; i < n ; i ++) {
double A = - (pi[0].y - pi[1].y - pi[i].y + pi[i + 1].y) ;
double B = - (pi[1].x - pi[0].x - pi[i + 1].x + pi[i].x) ;
double C = Cross(pi[i] , pi[i + 1]) - Cross(pi[0] , pi[1]) ;
if(sgn(B) == 0) {
if(sgn(A) > 0) l[++cnt] = Line ( (Vec) { - C / A , 0 } , (Vec) { - C / A , -1 } ) ;
else l[++cnt] = Line ( (Vec) { - C / A , 0 } , (Vec) { - C / A , 1 } ) ;
}
else if(sgn(B) > 0)
l[++cnt] = Line (Vec(0 , f(0 , A , B , C)) , Vec(1 , f(1 , A , B , C))) ;
else
l[++cnt] = Line (Vec(1 , f(1 , A , B , C)) , Vec(0 , f(0 , A , B , C))) ;
}
SI() ;
p[tail + 1] = p[head] ;
for(int i = head ; i <= tail ; i ++)
ans += Cross(p[i] , p[i + 1]) ;
printf("%.4lf
",ans / tot) ;
return 0 ;
}