作者在 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 <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);
}
#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);
}