Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贴一段暴力代码,ac 16ms~

Posted by xc19881023 at 2016-04-27 19:31:57 on Problem 3565
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator