[bzoj4445] [SCOI2015]小凸想跑步（半平面交）

题意：凸包上一个点\(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;

}

巴特西

[bzoj4445] [SCOI2015]小凸想跑步（半平面交）

最新文章

热门文章

巴特西

[bzoj4445] [SCOI2015]小凸想跑步 （半平面交）

最新文章

热门文章

[bzoj4445] [SCOI2015]小凸想跑步（半平面交）