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;
}