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 nazgul1991 at 2010-09-08 23:10:47 on Problem 2007
试了半天发现只有sort可以过,改成qsort死活过不了。。。迫不得已直接暴力排序,结果还是WA。。。。
跪求大家给个解释,小菜在次跪谢了~~~
//直接写了个排序WA...
#include <stdio.h>
#include <stdlib.h>

const int MAXN = 60;

typedef struct
{
	int x, y;
}POINT, *PPOINT;
POINT pd[MAXN], pu[MAXN];

int cmp( POINT a, POINT  b )
{
	if ( a.x*b.y > b.x*a.y )
		return 0;
	return 1;
}

void Paixu( PPOINT s, int l )
{
	int i, j;
	POINT p;
	for ( i=0; i<l; ++i )
	for ( j=i+1; j<l; ++j )
		if ( cmp( s[i], s[j] ) )
		{
			p = s[i]; s[i] = s[j]; s[j] = p;
		}
}

int main()
{
    int dl, ul, xx, yy, i;
	dl = ul = 0;
	//freopen( "//home//administrator//1.in", "r", stdin );
	scanf( "%d%d", &xx, &yy );
	while ( scanf( "%d%d", &xx, &yy ) != EOF )
	{
		if ( yy > 0 )
		{
			pu[ul].x = xx; pu[ul].y = yy;
			ul++;
		}
		else
		{
			pd[dl].x = xx; pd[dl].y = yy;
			dl++;
		}
	}
	Paixu( pu, ul );
	Paixu( pd, dl );
	printf( "(0,0)\n" );
	for ( i=0; i<dl; ++i )
		printf( "(%d,%d)\n", pd[i].x, pd[i].y );
	for ( i=0; i<ul; ++i )
		printf( "(%d,%d)\n", pu[i].x, pu[i].y );
	return 0;
}
//sort,AC程序。。。
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;

struct Point
{
	int x, y;
}p[60];

bool cmp( Point a, Point b )
{
    int temp;
    temp = a.x*b.y - a.y*b.x;
    if ( temp > 0 ) return true;
    return false;
}

int main()
{
    int l = 0, xx, yy, i;
	scanf( "%d%d", &xx, &yy );
	while ( scanf( "%d%d", &p[l].x, &p[l].y ) != EOF )
		l++;
	sort( p, p + l, cmp );
	printf( "(0,0)\n" );
	for ( i=0; i<l; ++i )
		printf( "(%d,%d)\n", p[i].x, p[i].y );
	return 0;
}
//qsort死活过不了的。。。
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

const int MAXN = 155;

struct Point
{
	int x, y;
}pd[MAXN], pu[MAXN];

int cmp( const void *a, const void *b )
{
	struct Point *p, *q;
	int i;
	p = ( struct Point * )a; q = ( struct Point * )b;
	i = p->x*q->y - p->y*q->x;
	if ( i > 0 ) return 1;
	return 0;
}

int main()
{
    int dl, ul, xx, yy, i;
	dl = ul = 0;
	//freopen( "//home//administrator//1.in", "r", stdin );
	scanf( "%d%d", &xx, &yy );
	while ( scanf( "%d%d", &xx, &yy ) != EOF )
	{
		pu[ul].x = xx; pu[ul].y = yy;
		ul++;
	}
	qsort( pu, ul, sizeof( pu[0] ), cmp );
	printf( "(0,0)\n" );
	for ( i=0; i<ul; ++i )
		printf( "(%d,%d)\n", pu[i].x, pu[i].y );
	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