【BZOJ 1020】 [SHOI2008]安全的航线flight

1020: [SHOI2008]安全的航线flightTime Limit:1 SecMemory Limit:162 MBSubmit:754Solved:243[Submit][Status]Description

在设计航线的时候，安全是一个很重要的问题。首先，最重要的是应采取一切措施确保飞行不会发生任何事故，但同时也需要做好最坏的打算，一旦事故发生，就要确保乘客有尽量高的生还几率。当飞机迫降到海上的时候，最近的陆地就是一个关键的因素。航线中最危险的地方就是距离最近的陆地最远的地方，我们称这种点为这条航线“孤地点”。孤地点到最近陆地的距离被称为“孤地距离”。作为航空公司的高级顾问，你接受的第一个任务就是尽量找出一条航线的孤地点，并计算这条航线的孤地距离。为了简化问题，我们认为地图是一个二维平面，陆地可以用多边形近似，飞行线路为一条折线。航线的起点和终点都在陆地上，但中间的转折点是可能在海上（如下图所示，方格标示出了孤地点）。

Input

输入的第一行包括两个整数C和N（1≤C≤20，2≤N≤20），分别代表陆地的数目的航线的转折点的数目。接下来有N行，每行有两个整数x,y。(x,y)表示一个航线转折点的坐标，第一个转折点为航线的起点，最后一个转折点为航线的终点。接下来的输入将用来描述C块大陆。每块输入由一个正整数M开始（M≤30），M表示多边形的顶点个数，接下来的M行，每行会包含两个整数x,y，(x,y)表示多边形的一个顶点坐标，我们保证这些顶点以顺时针或逆时针给出了该多边形的闭包，不会出现某些边相交的情况。此外我们也保证输入数据中任何两块大陆不会相交。输入的所有坐标将保证在-10000到10000的范围之间。

Output

输出一个浮点数，表示航线的孤地距离，数据保留2位小数。

Sample Input

1 2-9 -65 130 16-16 -1217 -6

Sample Output

0.00

HINTSource

NWERC 2007

计算几何之迭代法。

在莫涛的论文中有讲解。

大概做法是：

1.首先把航线上的所有线段加入队列

2.对于每一条线段

（1）我们首先找到线段左右端点的陆地最近点为p1,p2

（2）用二分法找到这条线段上与p1,p2几乎等距的点x，且这个距离为d

（3）那么整条线段上的点到最近陆地的距离一定不会超过d。 为什么呢？

首先x到最近陆地的距离一定<=d；然后如果从x向左端点走，那么离p1越来越近，，到p1的距离<d，就有了保底了；对于向右走同理。

（4）如果这个d小于等于当前的ans,那么整条线段可以舍弃了；否则把左端点到x的线段以及x到右端点的线段都加入队列

3.当队列为空时算法结束

#include <iostream>#include <cmath>#include <algorithm>#include <cstring>#include <cstdio>#include <cstdlib>#define eps 1e-16#define MQ 100000#define M 50using namespace std;int n,m;double ans;int dcmp(double x){if (fabs(x)<eps) return 0;return x>eps?1:-1;}struct Point {double x,y;Point() {}Point(double x,double y): x(x),y(y) {}void read(){scanf("%lf %lf",&x,&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,double p){return Point(a.x*p,a.y*p);}friend Point operator / (Point a,double p){return Point(a.x/p,a.y/p);}friend bool operator == (Point a,Point b){return !dcmp(a.x-b.x)&&!dcmp(a.y-b.y);}}flight[M];typedef Point Vector;double Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}double Len(Vector a){return sqrt(Dot(a,a));}double Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}bool On(Point a,Point b,Point c){return !dcmp(Cross(b-a,c-a))&&dcmp((a.x-b.x)*(a.x-c.x))<=0&&dcmp((a.y-b.y)*(a.y-c.y))<=0;}bool inter(Point a,Point b,Point c,Point d){return dcmp(Cross(b-a,c-a)*Cross(b-a,d-a))<=0&&dcmp(Cross(d-c,a-c)*Cross(d-c,b-c))<=0;}Vector Normal(Vector a){return Vector(-a.y,a.x);}struct Seg{Point a,b;Seg() {}Seg(Point a,Point b):a(a),b(b) {}}queue[1000000+5];struct Polygon{Point p[M];int tot;bool In(Point &point){int total=0;for (int i=1;i<=tot;i++)if (On(point,p[i],p[i%tot+1]))return true;Point ray=Point(-10001,point.y);for (int i=1;i<=tot;i++)total+=inter(ray,point,p[i],p[i%tot+1]);return total&1;}}island[M];struct near{Point P;double dis;near() {}near(Point a,double b): P(a),dis(b) {}};void init(){scanf("%d%d",&n,&m);for (int i=1;i<=m;i++)flight[i].read();for (int i=1;i<=n;i++){scanf("%d",&island[i].tot);for (int j=1;j<=island[i].tot;j++)island[i].p[j].read();}}bool check(Point p){for (int i=1;i<=n;i++)if (island[i].In(p))return true;return false;}Point Getinter(Point a,Vector b,Point c,Vector d) //求垂足{Vector u=a-c;double t=Cross(d,u)/Cross(b,d);return a+b*t;}near DISPS(Point a,Point b,Point c){if (b==c) return near(b,Len(b-a));Vector v1=c-b,v2=a-b,v3=a-c;if (dcmp(Dot(v1,v2)<=0)) return near(b,Len(v2));if (dcmp(Dot(v1,v3)>=0)) return near(c,Len(v3));Vector v=Normal(b-c);//求与bc垂直的向量Point ans=Getinter(a,v,b,v1);return near(ans,Len(a-ans));}near Find(Point &p) //找最近点{if (check(p)) return near(p,0);near ans1;ans1.dis=1<<30;for (int i=1;i<=n;i++)for (int j=1;j<=island[i].tot;j++){near get=DISPS(p,island[i].p[j],island[i].p[j%island[i].tot+1]);if (dcmp(ans1.dis-get.dis)>=0) ans1=get;}ans=max(ans,ans1.dis);return ans1;}void Solve(){int front=0,rear=0;for (int i=1;i<m;i++)queue[++rear]=Seg(flight[i],flight[i+1]),Find(flight[i]);Find(flight[m]); Seg head;while (front!=rear){head=queue[front=front%MQ+1];Point p1=Find(head.a).P,p2=Find(head.b).P,l=head.a,r=head.b,mid=(l+r)/2;while (Len(r-l)>1e-4){Point mid=(l+r)/2;if (Len(mid-p1)<Len(mid-p2)) l=mid;else r=mid;}double nowans=min(Len(l-p1),Len(l-p2));Find(l);if (ans+0.005<nowans)queue[rear=rear%MQ+1]=Seg(head.a,mid),queue[rear=rear%MQ+1]=Seg(mid,head.b);}}int main(){init();Solve();printf("%.2lf\n",ans);return 0;}

感悟：

1.代码基本抄自ydc，略有改动。

在每一个结构体中：

near() {}near(Point a,double b): P(a),dis(b) {}这样的语句是为了方便赋值的，不加第一句会编译错误。

2.这道题中求与p1,p2等距的点的过程相当于一个剪枝过程

没有了爱的语言，所有的文字都是乏味的