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

凸包都不是,水排序,诶,这么多人WA,太弱了吧

Posted by root123 at 2012-09-01 15:27:22 on Problem 2007
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;

#define eps 1e-8
#define inf 1<<29

struct point
{
	int x, y;
}p[52];

int det(int x1, int y1, int x2, int y2)
{
	return x1 * y2 - x2 * y1;
}

int cross(point o, point a, point b)
{
	return det(a.x - o.x, a.y - o.y, b.x - o.x, b.y - o.y);
}

double f(int x)
{
	return x * x * 1.0;
}

double dis(point a, point b)
{
	return sqrt( f(a.x - b.x) + f(a.y - b.y) );
}

bool cmp(point a, point b)
{
	int tmp = cross(p[0], a, b);
	if(tmp > 0) return 1;
	if(tmp == 0 && dis(p[0], a) < dis(p[0], b) )return 1;
	return 0;
}

int main()
{
	int i, j;
	int n = 0;
	//freopen("int.txt", "r", stdin);
	while( ~scanf("%d%d", &p[n].x, &p[n].y) )
	{
		if(p[n].y < p[0].y) swap(p[0], p[n]);
		else if(p[n].y == p[0].y && p[n].x < p[0].x) swap(p[0], p[n]);
		n++;
	}
	sort(p + 1, p + n, cmp);
	for(i = 0; i < n; i++)
		if(p[i].x == 0.0 && p[i].y == 0.0){ j = i; break; }
	for(i = j; i < n; i++)
		printf("(%d,%d)\n", p[i].x, p[i].y);
	for(i = 0; i < j; i++)
		printf("(%d,%d)\n", p[i].x, p[i].y);
}

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