pku1066TreasureHunt

作者在 2010-07-30 21:01:21 发布以下内容
题目链接:pku1066(经典)
代码一:线段相交+枚举
//0 <= n <= 30  

#include<iostream>
#include <algorithm>
#include<cmath>
using namespace std;
struct point
{   double x,y;  };
struct line
{   point s, e;  };
double max(double a,double b)
{    return a>b?a:b;        }
double min(double a,double b)
{    return a<b?a:b;        }
//计算叉积
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);}
//判断线段相交
bool is_cross(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(s2,e1,s1)*multi(e1,e2,s1)>=0&&
          multi(s1,e2,s2)*multi(e2,e1,s2)>=0;
}
int main()
{
    int n;
    line ss[35];
    point p;
    int i,j,k;
    int node1,node2,min;
    while(cin>>n)
    {
        for(i=0;i<n;i++)
           cin>>ss[i].s.x>>ss[i].s.y>>ss[i].e.x>>ss[i].e.y;
        cin>>p.x>>p.y;min=100;
        for(i=0;i<n;i++)
        {
            node1=0;node2=0;
            for(j=0;j<n;j++)
            {
                if(is_cross(ss[i].s,p,ss[j].s,ss[j].e))node1++;
                if(is_cross(ss[i].e,p,ss[j].s,ss[j].e))node2++;
            }
            if(node1<min)min=node1;
            if(node2<min)min=node2;
        }
        if(n)printf("Number of doors = %d\n",min);
        else printf("Number of doors = 1\n");
    }
    return 0;
}

//线段相交

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
double const EPS = 1e-8;
const int INF = 1<<30;

int dcmp(double x){return x < -EPS ? -1 : x > EPS;}

struct Point{
    double x,y;
    Point(){}
    Point(double a, double b):x(a), y(b){}
     bool operator<(Point a){return atan2(y - 50, x - 50) < atan2(a.y - 50, a.x - 50); }
};

struct Line{Point a, b;};

Point P[128], s, t;
Line L[36];
int n, cnt, best;

double xmult(Point p1, Point p2 , Point p0)
{
     return (p1.x - p0.x)*(p2.y - p0.y)-(p2.x - p0.x)*(p1.y - p0.y);
}
bool same_side(Point p1, Point p2, Line L)
{
     return dcmp(xmult(L.b, p1, L.a) * xmult(L.b, p2, L.a)) >= 0;
}

int main()
{
    int i, j, ans;
     best = INF; cnt = 0;
    P[cnt++] = Point(0, 0);
     P[cnt++] = Point(100, 0);
     P[cnt++] = Point(0, 100);
     P[cnt++] = Point(100, 100);

     cin >> n;
     for(i = 0; i < n; i++)
     {
         cin>> L[i].a.x >> L[i].a.y >> L[i].b.x >> L[i].b.y;
         P[cnt++] = L[i].a;
         P[cnt++] = L[i].b;
     }
     cin>> s.x >> s.y;

     sort(P, P+cnt);

     for(i = 0; i < cnt; i++ )
     {
         ans = 0;
         t = Point( (P[i].x + P[(i+1)%cnt].x)/2, (P[i].y + P[(i+1)%cnt].y)/2 );
         for(j = 0; j < n; j++)
             if(!same_side(s, t, L[j]))ans++;
         if(ans < best) best = ans;
     }

     printf("Number of doors = %d\n", best+1);
}

 
计算几何 | 阅读 838 次
文章评论,共0条
游客请输入验证码
最新评论