bzoj2033:[2009国家集训队]大灾变(半平面交)

Author Avatar
Sakits 3月 30, 2018

题解

  这题剧毒…死活拍不出错,而且坑点特别多
  其实是半平面交的模板题…说是半平面交但实际上这题并不用像求多边形的核那么麻烦,直接按水平可见直线那题的方法做就好了…
  大概就是把山的直线按斜率排序,一个一个塞进栈里,如果新加进去的直线与栈顶往下第二条直线的交点在栈顶两条直线的交点左边,那么栈顶那条直线一定被挡住了,就可以弹出。
  这样我们就能得到半平面交了,那么显然浮空岛就是半平面交里yy最小的点。但是瞭望塔就不一样了,因为它是相对高度,还要减去山脉的高度,显然在每个点建塔所需的高度是个分段一次函数,那么最值一定是在端点处,枚举所有端点计算答案即可。
  有一些细节。0-0得特判掉,左右得插两个竖直的半平面,调了好久…
  说一下自己调了好久的一个问题…判断交点是否在左边要根据yy的大小,因为左右两边有两个竖直的半平面,如果与这两个平面相交判断交点xx精度不够…

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=1000010, inf=1e9;
const double eps=1e-5;
struct line{double k, b;}l[maxn], L[maxn], st[maxn];
struct poi{double x, y;}p[maxn], a[maxn];
int n, cnt, top;
bool operator < (line a, line b){return b.k-a.k>eps || (fabs(b.k-a.k)<eps && a.b-b.b>eps);}
bool operator < (poi a, poi b){return a.x<b.x;}
inline double X(line a, line b){return (a.b-b.b)/(b.k-a.k);}
inline double Y(line a, double x){return a.k*x+a.b;}
inline void makeline(poi a, poi b)
{
	l[++cnt].k=(a.y-b.y)/(a.x-b.x);
	l[cnt].b=a.y-l[cnt].k*a.x;
}
inline double Fabs(double x)
{
	if(x<eps && x>-eps) return 0;
	return x;
}
inline bool check(line a, line b, line c)
{
	double x=X(a, b);
	return Y(c, x)-Y(b, x)>eps;
}
int main()
{
	scanf("%d", &n);
	for(int i=1;i<=n;i++) scanf("%lf", &a[i].x), scanf("%lf", &a[i].y);
	sort(a+1, a+1+n);
	for(int i=1;i<n;i++) makeline(a[i], a[i+1]);
	makeline((poi){a[1].x-eps, a[1].y+1e5}, a[1]); makeline(a[n], (poi){a[n].x+eps, a[n].y+1e5});
	for(int i=2;i<=n;i++) L[i]=l[i-1]; 
	sort(l+1, l+cnt+1);
	for(int i=1;i<=cnt;i++)
	{
		if(top) if(fabs(st[top].k-l[i].k)<eps) continue;
		while(top>1 && check(st[top], st[top-1], l[i])) top--;
		st[++top]=l[i];
	}
	double mnx=1e100, mny=1e100;
	for(int i=1;i<top;i++) 
	{
		p[i].x=X(st[i], st[i+1]), p[i].y=Y(st[i], p[i].x);
		if(p[i].y+eps<mny || (p[i].y==mny && p[i].x+eps<mnx)) mnx=p[i].x, mny=p[i].y; 
	}    
	double ans=1e100, mnx2, mny2;
	for(int i=2, j=1;i<top && j<=n;)
	{
		if(p[i].x+eps<a[j].x) 
		{
			if(ans>p[i].y-L[j].k*p[i].x-L[j].b+eps) 
			ans=p[i].y-L[j].k*p[i].x-L[j].b, mnx2=p[i].x, mny2=p[i].y;
			i++;
		}
		else
		{
			if(ans>st[i].k*a[j].x+st[i].b-a[j].y+eps)
			ans=st[i].k*a[j].x+st[i].b-a[j].y, mnx2=a[j].x, mny2=st[i].k*a[j].x+st[i].b;
			j++;
		}
	}
	mnx2=Fabs(mnx2); mny2=Fabs(mny2); mnx=Fabs(mnx); mny=Fabs(mny);
	printf("%.2lf %.2lf\n%.2lf %.2lf", mnx2, mny2, mnx, mny);
}