Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

看了discuss顿时觉得此题好水的说

Posted by ecjtu_yuweiwei at 2014-07-19 18:43:25 on Problem 1066
/*
题意:说白点就是一张图,里面有许多交叉的线【也可以说墙】(线的两端只能落在外围的四条边上并且不存在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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator