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到郁闷,以前melkman做的现在graham竟然过不了,求解!!!

Posted by coolsea at 2012-10-31 20:55:47 on Problem 1113
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const double Pi = acos(-1.0);
const int MAXN = 10010;

struct Pt{
	int x, y;
}p[MAXN];

int top;
int s[MAXN];

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

int cross(Pt a, Pt b, Pt c)
{
	return Xmul((b.x - a.x), (b.y - a.y), (c.x - a.x), (c.y - a.y));
}

int cmp(Pt a, Pt b)
{
	if(a.y == b.y)
		return a.x < b.x;
	return a.y < b.y;
}

void graham(int n)
{
	int i;
	sort(p + 1, p + n + 1, cmp);

	s[1] = 1;
	s[2] = 2;
	top = 2;

	for(i = 3; i <= n; i ++)
	{
		while(top > 1 && cross(p[s[top - 1]],p[s[top]],p[i]) <= 0)
			top --;
		s[++ top] = i;
	}

	int len = top;
	s[++top] = n - 1;

	for(i = n - 2; i >= 1; i --)
	{
		while(top > len && cross(p[s[top - 1]],p[s[top]],p[i]) <= 0)
			top --;
		s[++top] = i;
	}
}

double dist(Pt a, Pt b)
{
	return sqrt(0.0 + (a.x - b.x) * (a.x - b .x) + (a.y - b.y) * (a.y - b.y));
}

double solve(int n)
{
	double sum  = 0;
	graham(n);

	for(int i = 1; i < top; i ++)
		sum += dist(p[s[i]],p[s[i + 1]]);
	return sum;
}
int main()
{
	int n,l;
	int i,j;

	while(scanf("%d%d",&n,&l) != EOF)
	{
		memset(p,0,sizeof(p));
		memset(s,0,sizeof(s));

		for(i = 1; i <= n; i ++)
			scanf("%d%d",&p[i].x, & p[i].y);

		double sum = solve(n);
		sum += 2 * Pi * l;

		printf("%.0lf\n",sum);
	}

	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