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