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