| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
看了discuss顿时觉得此题好水的说/*
题意:说白点就是一张图,里面有许多交叉的线【也可以说墙】(线的两端只能落在外围的四条边上并且不存在3两条相同的线和三条线交于同一点)
这些线组成许多密闭的空间,其中一个密闭空间中藏有宝藏,问你怎样炸掉最少的墙到宝藏处,起点是从外围的四条线(四条线的坐标固定,题目给了)任意点进入
思路:其实题目上说要从每个内墙的中点进入,但是仔细想一想不管从不从中点你不可能“绕过”这堵墙,所以从墙的两个端点进入和中点进入效果一样的,所以题目就可以简化成
从给出线段交与外围墙上的每个端点与所有所给线的交点(除了本身)最少数目再加上外围一堵墙(即+1)就是题目所求
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define eps 1e-8
const int Max=101;
int sum[Max];
using namespace std;
int sign(double x)
{
return (x>eps)-(x<-eps);
}
typedef struct Node
{
double x;
double y;
}point;
point s[Max];
double multi(point p0,point p1,point p2)//叉积
{
return(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
//相交返回true,否则为false,接口为两线段的端点
bool IsIntersected(point s1,point e1,point s2,point e2)//两个线段相交
{
return(max(s1.x,e1.x)>=min(s2.x,e2.x))&& (max(s2.x,e2.x)>=min(s1.x,e1.x))&&(max(s1.y,e1.y)>=min(s2.y,e2.y))&&(max(s2.y,e2.y)>=min(s1.y,e1.y))&&(multi(s1,s2,e1)*multi(s1,e1,e2)>0)&&(multi(s2,s1,e2)*multi(s2,e2,e1)>0);
}
int main()
{
int n,i,j;
point ed;
//while(1)
//{
cin>>n;
memset(sum,0,sizeof(sum));
for(i=1;i<=2*n;i+=2)
{
cin>>s[i].x>>s[i].y>>s[i+1].x>>s[i+1].y;
}
cin>>ed.x>>ed.y;
for(i=1;i<=2*n;i++)
{
for(j=1;j<=2*n;j+=2)
{
if(i!=j)
{
if(IsIntersected(s[i],ed,s[j],s[j+1]))
sum[i]+=1;
}
}
}
if(n>0)
sort(sum+1,sum+(2*n));
if(n!=0)
cout<<"Number of doors = "<<sum[1]+1<<endl;
else
cout<<"Number of doors = "<<1<<endl;
//}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator