1012
POJ 3565 調整思想
題意：給出幾個蟻群 ，螞蟻的食物是蘋果樹，要求每個蟻群去蘋果樹的路徑是線段並且任意兩條路徑不能相交，給出蟻群坐標、蘋果樹坐標，求出任意一組解決方案。
這題就不斷的調整，如果當前的兩條線段相交的話就交換兩個點的位置，知道沒有相交的線段。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct point
{
int x,y;
};
int 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)
{
int 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;
}
int main()
{
point data1[105],data2[105];
int n,ans[105];
while(~scanf("%d",&n))
{
for(int i=1; i<=n; i++)
scanf("%d%d",&data1[i].x,&data1[i].y);
for(int i=1; i<=n; i++)
scanf("%d%d",&data2[i].x,&data2[i].y);
for(int i=1; i<=n; i++)
ans[i]=i;
while(1)
{
int f=1;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if(j!=i&&Segment_Intersect(data1[i],data2[ans[i]],data1[j],data2[ans[j]]))
swap(ans[i],ans[j]),f=0;
if(f)
break;
}
for(int i=1; i<=n; i++)
printf("%d%c",ans[i],i<n?' ':'\n');
}
return 0;
}
最後更新：2017-04-03 18:52:03