【bzoj1020】[SHOI2008]安全的航线flight

2015.04.23 10:32 Thu | 6次阅读 | 旧日oi | 固定链接 | 源码

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 -6
5 1
3
0 16
-16 -12
17 -6

Sample Output

0.00

题解

好恶心的一道题……计算几何好讨厌- -||
题解可以参照
http://www.myext.cn/other/a_30165.html
http://ydcydcy1.blog.163.com/blog/static/21608904020131492229367/
代码很复杂……
一定得找个时间写一套自己的计算几何模板。

我的程序

#include <bits/stdc++.h>
#define eps 1e-16
using namespace std;
int c,n;
double ans;
struct Point
{
    double x,y;
    Point(double _,double __):x(_),y(__){}
    Point(){}
}flight[25];
int dcmp(double p)
{
    if(fabs(p)<eps) return 0;
    return p>eps?1:-1;
}
Point operator +(Point a,Point b)
{
    return Point(a.x+b.x,a.y+b.y);
}
bool operator ==(const Point a,const Point b)
{
    return !dcmp(a.x-b.x)&&!dcmp(a.y-b.y);
}
Point operator /(const Point a,double k)
{
    return Point(a.x/k,a.y/k);
}
Point operator -(const Point a,const Point b)
{
    return Point(a.x-b.x,a.y-b.y);
}
Point operator *(const Point a,double b)
{
    return Point(a.x*b,a.y*b);
}
double dot(const Point &a,const Point &b)
{  
    return a.x*b.x+a.y*b.y;  
}
double len(const Point &a)
{  
    return sqrt(dot(a,a));  
}
double cross(const Point &a,const Point &b)
{  
    return a.x*b.y-a.y*b.x;  
}
Point normal(const Point &a)
{  
    return Point(-a.y,a.x); 
}
bool on(const Point &a,const Point &b,const 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(const Point &a,const Point &b,const Point &c,const Point &d)
{
    return dcmp(cross(c-a,b-a)*cross(d-a,b-a))<=0&&dcmp(cross(a-c,d-c)*cross(b-c,d-c))<=0;
}
Point get_inter(const Point &a,const Point &b,const Point &c,const Point &d)
{
    Point u=a-c;
    double t=cross(d,u)/cross(b,d);
    return a+b*t;
}
struct Polygon
{
    Point x[35];
    int num;
    bool in(Point &p)
    {
        int tot=0;
        for(int i=1;i<=num;i++)
            if(on(p,x[i],x[i%num+1])) return 1;
        Point ray=Point(-10001,p.y);
        for(int i=1;i<=num;i++)
            tot=tot+inter(ray,p,x[i],x[i%num+1]);
        return tot&1;
    }
}land[25];
struct seg
{
    Point a,b;
    seg(Point _,Point __):a(_),b(__){}
    seg(){}
};
queue<seg> q;
struct near
{
    Point p;
    double dis;
    near(Point _,double __):p(_),dis(__){}
    near(){}
};
near get_dis(const Point &a,const Point &b,const Point &c)
{
    if(b==c) return near(b,len(b-a));
    Point 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));
    Point v=normal(b-c);
    Point ans=get_inter(a,v,b,v1);
    return near(ans,len(a-ans));
}
near find(Point &p)
{
    for(int i=1;i<=c;i++)
        if(land[i].in(p)) return near(p,0);
    near ans1;ans1.dis=1<<30;
    for(int i=1;i<=c;i++)
        for(int j=1;j<=land[i].num;j++)
        {
            near get=get_dis(p,land[i].x[j],land[i].x[j%land[i].num+1]);
            if(dcmp(ans1.dis-get.dis)>=0) ans1=get;
        }
    ans=max(ans,ans1.dis);
    return ans1;
}
int main()
{
    cin>>c>>n;
    for(int i=1;i<=n;i++)
        scanf("%lf%lf",&flight[i].x,&flight[i].y);
    for(int i=1;i<=c;i++)
    {
        scanf("%d",&land[i].num);
        for(int j=1;j<=land[i].num;j++)
            scanf("%lf%lf",&land[i].x[j].x,&land[i].x[j].y);
    }
    for(int i=1;i<n;i++)
        q.push(seg(flight[i],flight[i+1])),find(flight[i]);
    find(flight[n]);
    while(!q.empty())
    {
        seg now=q.front();q.pop();
        Point p1=find(now.a).p,p2=find(now.b).p,l=now.a,r=now.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=max(len(l-p1),len(l-p2));
        find(l);
        if(ans+0.005<nowans) q.push(seg(now.a,mid)),q.push(seg(mid,now.b));
    }
    printf("%.2lf\n",ans);
    return 0;
}```