| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
贴一段暴力代码,ac 16ms~#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxN=105;
const double eps=1e-8;
int n,match[maxN];
struct point
{
double x,y;
};
point ant[maxN],apple[maxN];
inline double dis(const point &a,const point &b)
{
return sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));
}
void init()
{
scanf("%d",&n);
for (int i = 1; i <= n; i++)
scanf("%lf%lf",&ant[i].x,&ant[i].y),match[i]=i;
for (int i = 1; i <= n; i++)
scanf("%lf%lf",&apple[i].x,&apple[i].y);
}
inline double outer_product(const point &a,const point &b,const point &c)
{
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
bool across(const point &a,const point &b,const point &c,const point &d)
{
return outer_product(a,b,c)*outer_product(a,b,d)<-eps&&outer_product(c,d,a)*outer_product(c,d,b)<-eps;
}
int main()
{
// freopen("D:\\input.txt","r",stdin);
init();
bool ok=false;
while (!ok)
{
ok=true;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (j!=i&&across(ant[i],apple[match[i]],ant[j],apple[match[j]]))
swap(match[i],match[j]),ok=false;
}
for (int i = 1; i <= n; i++) printf("%d\n",match[i]);
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator