题意:

感谢Jimmy Carlson Wang的翻译!

给你n只蚂蚁n个苹果树,要你把它们配对起来

使得它们的连线不相交

Warning:算法正确性没有证明过

求看Blog的神犇帮忙证明

一开始乱分一个

之后进行1000次调整,如果a和b撞上了,就交换a和b对应的点

果然好久没写叉积了还写错了一次...

不管怎么样AC的还算挺快

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct point
{
    int x;
    int y;
    void read()
    {
        scanf("%d%d",&x,&y);
    }
    friend point operator - (const point &a,const point &b)
    {
        point c=a;
        c.x-=b.x;
        c.y-=b.y;
        return c;
    }
};
int cross_mul(const point &a,const point &b)
{
    return a.x*b.y-b.x*a.y;
}
bool cross(const point &a,const point &b,const point &c,const point &d)
{
    if ((long long)cross_mul(a-b,a-c)*cross_mul(a-b,a-d)>0) return 0;
    if ((long long)cross_mul(c-d,c-a)*cross_mul(c-d,c-b)>0) return 0;
    return 1;
}
point a[105];
point b[105];
int c[105];
int main()
{
    freopen("ants.in","r",stdin);
    freopen("ants.out","w",stdout);
    int n;
    scanf("%d",&n);
    int i;
    for (i=0;i<n;i++)
    {
        a[i].read();
    }
    for (i=0;i<n;i++)
    {
        b[i].read();
    }
    for (i=0;i<n;i++)
    {
        c[i]=i;
    }
    for (i=0;i<1000;i++)
    {
        int j,k;
        for (j=0;j<n;j++)
        {
            for (k=j+1;k<n;k++)
            {
                if (cross(a[j],b[c[j]],a[k],b[c[k]]))
                {
                    swap(c[j],c[k]);
                }
            }
        }
    }
    for (i=0;i<n;i++)
    {
        printf("%d\n",c[i]+1);
    }
    return 0;
}