48
POJ 2653 暴力判斷線段相交
題意是按照輸入的先後順序放木棍，然後輸出最上層的木棍，何為最上層，就是木棍上方沒有木棍和它相交就行。
這題坑爹啊，一直TLE後來才發現最上層木棍不是底下的木棍數最多而是隻要上方沒有木棍就行。所以隻需要開一個標記數組從前往後如果後麵有與它相交的那麼這個木棍肯定不是最上層的，知道這些再知道線段相交的模板就可以A了。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef double PointType;
struct point
{
PointType x,y;
};
PointType Direction(point pi,point pj,point pk) //判斷向量PiPj在向量PiPk的順逆時針方向 +順-逆0共線
{
return (pj.x-pi.x)*(pk.y-pi.y)-(pk.x-pi.x)*(pj.y-pi.y);
}
bool On_Segment(point pi,point pj,point pk)
{
if(pk.x>=min(pi.x,pj.x)&&pk.x<=max(pi.x,pj.x)&&pk.y>=min(pi.y,pj.y)&&pk.y<=max(pi.y,pj.y))
return 1;
return 0;
}
bool Segment_Intersect(point p1,point p2,point p3,point p4)
{
PointType d1=Direction(p3,p4,p1),d2=Direction(p3,p4,p2),d3=Direction(p1,p2,p3),d4=Direction(p1,p2,p4);
if(((d1>0&&d2<0)||(d1<0&&d2>0))&&((d3>0&&d4<0)||(d3<0&&d4>0)))
return 1;
if(d1==0&&On_Segment(p3,p4,p1))
return 1;
if(d2==0&&On_Segment(p3,p4,p2))
return 1;
if(d3==0&&On_Segment(p1,p2,p3))
return 1;
if(d4==0&&On_Segment(p1,p2,p4))
return 1;
return 0;
}
point data[100005][2];
bool bj[100005];
int main()
{
int n;
while(~scanf("%d",&n),n)
{
memset(bj,0,sizeof(bj));
int maxnum=0,ansnum=0;
for(int i=0; i<n; i++)
scanf("%lf%lf%lf%lf",&data[i][0].x,&data[i][0].y,&data[i][1].x,&data[i][1].y);
for(int i=0; i<n; i++)
for(int j=i+1; j<n; j++)
if(Segment_Intersect(data[i][0],data[i][1],data[j][0],data[j][1]))
{
bj[i]=1;
break;
}
int f=0;
printf("Top sticks:");
for(int i=0; i<n; i++)
if(!bj[i])
{
if(f==0)
f=1,printf(" %d",i+1);
else
printf(", %d",i+1);
}
puts(".");
}
return 0;
}
最後更新：2017-04-04 07:03:55