题意：凸包上一个点\(p\)，使得\(p\)和点\(0,1\)组成的三角形面积最小 用叉积来求：\(p,i,i+1\)组成的三角形面积为： （\(\times\)为叉积）\((p_p-i)\times (p_p-p_{i+1})\Rightarrow\)\((x_p-x_i,y_p-y_i)\times(x_p-x_{i+1},y_p-y_{i+1})\Rightarrow\)\((x_p-x_i)(y_p-y_{i+1})-(y_p-y_i)(x_p-x_{i+1})\Rightarrow\)\(x_py_p-x_py_{i+1}-x_iy_p+x_iy_{i+1}-x_py_p+x_{i+1}y_p+x_py_i-x_{i+1}y_i\Rightarrow\)\(x_p(y_i-y_{i+1})+y_p(x_{i+1}-x_i)+(x_iy_{i+1}-x_{i+1}y_i)\) 要求点\(p\)和点\(0,1\)组成的三角形面积最小，即：\(x_p(y_0-y_1)+y_p(x_1-x_0)+(x_0y_1-x_1y_0)<x_p(y_i-y_{i+1})+y_p(x_{i+1}-x_i)+(x_iy_{i+1}-x_{i+1}y_i)\Rightarrow\)\(x_p(y_0-y_1-y_i+y_{i+1})+y_p(x_1-x_0-x_{i+1}+x_i)+(x_0y_1-x_1y_0-x_iy_{i+1}+x_{i+1}y_i)<0\) 可以发现，方程为\(ax+by+c<0\)的形式，可以求出\(n\)个方程，和原凸多边形求一下半平面交，交出来的面积与原多边形面积的比值即为答案
#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<cmath> #include<algorithm> #include<queue> #include<stack> #include<set> #include<bitset> #include<sstream> #include<cstdlib> #define QAQ int #define TAT long long #define OwO bool #define ORZ double #define Ug unsigned #define F(i,j,n) for(QAQ i=j;i<=n;++i) #define E(i,j,n) for(QAQ i=j;i>=n;--i) #define MES(i,j) memset(i,j,sizeof(i)) #define MEC(i,j) memcpy(i,j,sizeof(j)) using namespace std; const QAQ N=300005; const ORZ eps=1e-8; QAQ sign(ORZ x){return fabs(x)<=eps ? 0 : (x>0 ? 1 : -1);} QAQ n; struct Point { ORZ x,y; Point(){} Point(ORZ X,ORZ Y){x=X;y=Y;} friend Point operator + (Point a,Point b){ return Point(a.x+b.x,a.y+b.y); } friend Point operator - (Point a,Point b){ return Point(a.x-b.x,a.y-b.y); } friend Point operator * (Point a,ORZ k){ return Point(a.x*k,a.y*k); } friend ORZ operator * (Point a,Point b){ return a.x*b.x+a.y*b.y; } friend ORZ operator ^ (Point a,Point b){ return a.x*b.y-a.y*b.x; } }p[N]; struct Line{ Point p,v; ORZ poa; Line(){} Line(Point a,Point b){ p=a;v=b; poa=atan2(b.y,b.x); } friend OwO operator < (Line a,Line b){ return sign(a.poa-b.poa)==0 ? sign((a.v) ^ (b.p-a.p)) >0 : sign(a.poa-b.poa)<0; } }a[N],q[N]; QAQ js,head,tail,cnt; ORZ s1,s2; Point inter(Line a,Line b){ Point u=a.p-b.p; ORZ k=(b.v^u)/(a.v^b.v); return a.p+a.v*k; } OwO pd(Line a,Point b){ return sign(a.v^(b-a.p))>=0; } void Half_Plane(){ sort(a+1,a+js+1); cnt=1; F(i,2,js) if(sign(a[i].poa-a[cnt].poa)>0) a[++cnt]=a[i]; head=1;tail=0; q[++tail]=a[1];q[++tail]=a[2]; F(i,3,cnt){ while(head<tail&&pd(a[i],inter(q[tail-1],q[tail]))) tail--; while(head<tail&&pd(a[i],inter(q[head+1],q[head]))) head++; q[++tail]=a[i]; } while(head<tail&&pd(q[head],inter(q[tail-1],q[tail]))) tail--; F(i,head,tail-1) p[i]=inter(q[i],q[i+1]); p[tail]=inter(q[tail],q[head]); F(i,head,tail-1) s2+=(p[i]^(p[i+1]-p[i])); s2+=(p[tail]^(p[head]-p[tail])); } QAQ main(){ scanf("%d",&n); F(i,0,n-1) scanf("%lf%lf",&p[i].x,&p[i].y); p[n]=p[0]; F(i,0,n-1) { a[++js]=Line(p[i+1],p[i]-p[i+1]); s1+=(p[i]^(p[i+1]-p[i])); } F(i,1,n-1){ ORZ A=p[i+1].x-p[i].x-p[1].x+p[0].x; ORZ B=p[i+1].y-p[i].y-p[1].y+p[0].y; ORZ C=-(p[i]^(p[i+1]-p[i]))+(p[0]^(p[1]-p[0])); if(sign(A)!=0) a[++js]=Line(Point(0,C/A),Point(-A,-B)); else if(sign(B)!=0) a[++js]=Line(Point(-C/B,0),Point(0,-B)); } Half_Plane(); printf("%.4lf\n",fabs(s2/s1)); return 0; }转载于:https://www.cnblogs.com/heower/p/8473944.html
