频道栏目
首页 > 考试 > 其他 > 正文

bzoj1137【POI2009】Wsp 岛屿

2016-05-20 09:25:33         来源:AaronPolaris  
收藏   我要投稿
Time Limit:10 SecMemory Limit:162 MBSecSpecial Judge

Description

Byteotia岛屿是一个凸多边形。城市全都在海岸上。按顺时针编号1到n。任意两个城市之间都有一条笔直的道路相连。道路相交处可以自由穿行。有一些道路被游击队控制了,不能走,但是可以经过这条道路与未被控制的道路的交点。问从城市1到n的最短距离。

Input

第一行正整数n m表示城市数和被控制的岛屿数(3≤n≤10^5 1≤m≤10^6)接下来n行每行两个整数x y表示每个城市的坐标。(|x|,|y|≤10^6)接下来m行描述一条不能走的道路(起点和终点)。数据保证有解。

Output

输出一个实数,最短距离,误差10^-5以内均算正确。

Sample Input

6 9
-12 -10
-11 6
-4 12
6 14
16 6
18 -2
3 4
1 5
2 6
2 3
4 5
3 5
1 3
3 6
1 6

Sample Output

42.000000000

HINT

 

Source

 

半平面交思路好题

因为1-n是顺时针排列,所以1-n的最短路径就是所有可以使用的线段的半平面交的长度。

然而这样也是不行的因为边最多会有O(n^2)条。

每个点出发的点,一定是越靠后越好,所以只要保存最靠后那条,这样边就只有O(n)条了。

 

#include<iostream>
#include<cstdlib>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 100005
#define maxm 1000005
#define eps 1e-8
using namespace std;
int n,m,cnt,tot;
double ans;
struct P
{
	double x,y;
	P(double xx=0,double yy=0){x=xx;y=yy;}
	friend P operator -(P a,P b){return P(a.x-b.x,a.y-b.y);}
	friend double operator *(P a,P b){return a.x*b.y-a.y*b.x;}
}p[maxn],a[maxn];
struct L
{
	P a,b;double angle;
	friend bool operator <(L a,L b)
	{
		if (fabs(a.angle-b.angle)<=eps) return (a.b-a.a)*(b.b-a.a)>0;
		else return a.angle<b.angle; struct="" edge="" int="" friend="" bool="" operator="" return="" a.x="=b.x?a.y">b.y:a.x<b.x;} inline="" int="" x="0,f=1;char" ch="" while="">'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline double dis(P a,P b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
inline P inter(L l1,L l2)
{
	double k1=(l2.b-l1.a)*(l1.b-l1.a),k2=(l1.b-l1.a)*(l2.a-l1.a),t=k1/(k1+k2);
	return P(l2.b.x+(l2.a.x-l2.b.x)*t,l2.b.y+(l2.a.y-l2.b.y)*t);
}
inline bool judge(L l1,L l2,L t)
{
	P p=inter(l1,l2);
	return (t.b-t.a)*(p-t.a)<-eps;
}
inline void hpi()
{
	F(i,1,cnt) l[i].angle=atan2(l[i].b.y-l[i].a.y,l[i].b.x-l[i].a.x);
	sort(l+1,l+cnt+1);
	int head=1,tail=0;tot=1;
	F(i,2,cnt)
	{
		if (fabs(l[i].angle-l[i-1].angle)>=eps) tot++;
		l[tot]=l[i];
	}
	cnt=tot;
	q[++tail]=l[1];q[++tail]=l[2];
	F(i,3,cnt)
	{
		while (head<tail&&judge(q[tail],q[tail-1],l[i])) while="" tot="0;" int="" n="read();m=read();" .x="" if="">e[i].y) swap(e[i].x,e[i].y);
	}
	sort(e+1,e+m+1);
	if (e[1].x!=1||e[1].y!=n)
	{
		printf("%.10lf\n",dis(p[1],p[n]));
		return 0;
	}
	int t=1;
	F(i,1,n-1)
	{
		int j=n;
		while (t<=m&&e[t].x==i&&e[t].y==j&&j>i) j--,t++;
		if (j>i) l[++cnt]=(L){p[j],p[i]};
		while (t<=m&&e[t].x==i) t++;
	}
	l[++cnt]=(L){p[1],p[n]};
	hpi();
	a[0]=a[tot];
	F(i,1,tot) ans+=dis(a[i],a[i-1]);
	ans-=dis(p[1],p[n]);
	printf("%.10lf\n",ans);
	return 0;
}

 

相关TAG标签 岛屿
上一篇:nyoj248 BUYING FEED(贪心orDP)
下一篇:bzoj3533【SDOI2014】向量集
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站