BZOJ_1020_[SHOI2008]_安全的航线flight_(计算几何+二分)

描述


http://www.lydsy.com/JudgeOnline/problem.php?id=1020

给出一条航线(折线),给出\(c\)个陆地(多边形).求航线上距离陆地的最近距离最远的距离.

分析


也是一道神题...

 #include <bits/stdc++.h>
using namespace std; const int maxn=+,maxm=+,maxq=1e6;
const double eps=1e-;
int c,n;
double ans;
inline int dcmp(double x){ if(fabs(x)<eps) return ; else return x>?:-; }
struct pt{
double x,y;
pt(double x=,double y=):x(x),y(y){}
pt operator + (const pt &a) const { return pt(x+a.x,y+a.y); }
pt operator - (const pt &a) const { return pt(x-a.x,y-a.y); }
pt operator * (const double &p) const { return pt(x*p,y*p); }
pt operator / (const double &p) const { return pt(x/p,y/p); }
pt normal(){ return pt(-y,x); }
bool operator == (const pt &a) const { return !dcmp(x-a.x)&&!dcmp(y-a.y); }
void read(){ scanf("%lf%lf",&x,&y); }
}A[maxn];
typedef pt vt;
inline double dot(vt a,vt b){ return a.x*b.x+a.y*b.y; }
inline double crs(vt a,vt b){ return a.x*b.y-a.y*b.x; }
inline double len(vt a){ return sqrt(dot(a,a)); }
struct sg{
pt a,b;
sg(){}
sg(pt a,pt b):a(a),b(b){}
bool on(const pt &p){ return !dcmp(crs(a-p,b-p))&&dcmp(dot(a-p,b-p))<; }
}q[maxq];
struct polygon{
int cnt; pt p[maxm];
bool in(const pt &a){
int wn=;
for(int i=;i<=cnt;i++){
if(sg(p[i],p[i%cnt+]).on(a)) return true;
int k=dcmp(crs(p[i%cnt+]-p[i],a-p[i]));
int d1=dcmp(p[i].y-a.y);
int d2=dcmp(p[i%cnt+].y-a.y);
if(k>&&d1<=&&d2>) wn++;
if(k<&&d2<=&&d1>) wn--;
}
return wn;
}
}land[maxn];
struct node{
pt p; double d;
node(){}
node(pt p,double d):p(p),d(d){}
};
inline pt get_l_int(pt p,vt v,pt q,vt w){
vt u=p-q;
double t=crs(w,u)/crs(v,w);
return p+v*t;
}
inline node dis_to_sg(pt p,pt a,pt b){
vt v1=b-a,v2=p-a,v3=p-b;
if(dcmp(dot(v1,v2)<)) return node(a,len(v2));
else if(dcmp(dot(v1,v3)>)) return node(b,len(v3));
else return node(get_l_int(p,v1.normal(),a,v1),fabs(crs(v1,v2)/len(v1)));
}
inline node find(pt a){
node t; t.d=<<;
for(int i=;i<=c;i++){
if(land[i].in(a)) return node(a,);
for(int j=;j<=land[i].cnt;j++){
node tmp=dis_to_sg(a,land[i].p[j],land[i].p[j%land[i].cnt+]);
if(dcmp(tmp.d-t.d)<) t=tmp;
}
}
ans=max(ans,t.d);
return t;
}
inline void init(){
scanf("%d%d",&c,&n);
for(int i=;i<=n;i++) A[i].read();
for(int i=;i<=c;i++){
scanf("%d",&land[i].cnt);
for(int j=;j<=land[i].cnt;j++) land[i].p[j].read();
}
}
inline void solve(){
int L=,R=;
for(int i=;i<n;i++) q[R++]=sg(A[i],A[i+]);
while(L!=R){
sg t=q[L++]; if(L==maxq) L=;
pt p1=find(t.a).p, p2=find(t.b).p,l=t.a,r=t.b,mid=(l+r)/;
while(len(l-r)>1e-){
mid=(l+r)/;
if(len(mid-p1)<len(mid-p2)) l=mid;
else r=mid;
}
double tmp=min(len(mid-p1),len(mid-p2));
if(ans+0.0001<tmp){
q[R++]=sg(t.a,mid); if(L==maxq) L=;
q[R++]=sg(mid,t.b); if(L==maxq) L=;
}
}
printf("%.2lf\n",ans);
}
int main(){
init();
solve();
return ;
}

1020: [SHOI2008]安全的航线flight

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 1021  Solved: 346
[Submit][Status][Discuss]

Description

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

BZOJ_1020_[SHOI2008]_安全的航线flight_(计算几何+二分)

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

HINT

Source

上一篇:定制的Server-Sent Events 聊天服务器


下一篇:IntelliJ IDEA(九) :酷炫插件系列