东大OJ-快速排序

1236: Simple Sort

时间限制: 1 Sec  内存限制: 128 MB
提交: 195  解决: 53
[提交][状态][讨论版]

题目描述

     You are given n two-dimension points randomly. Now you are asked to sort them by the following rule. For example , there are two points ,point A(x1,y1) and point B(x2,y2), to be compared. We define point A is less than point B if x1<x2. When x1 equals to x2, we define point A is less than point B if y1<y2. If x1 equals to x2 and y1 equals to y2, we say point A and point B are equal.

     Now you need to sort the points in non-descending order according the rules.

输入

    There are serval test cases.

    The first line contians a integer t which deticates the number of test cases.

    For each test case, the first line contians a integer n deticating the number of points in the test case. The next n lines contain two integers per line which are the positions of n points. (0<t<=100, 0<n<=10000, -1000<=x<=1000, -1000<=y<=1000)

输出

    For each test case, the first line print "Test case x:" in which number x is the test case number starting from 1. There are n lines following. Print out the result of the sort.

样例输入

3
3
10 2
5 4
3 9
3
7 8
8 4
7 5
1
4 4

样例输出

Test case 1:
3 9
5 4
10 2
Test case 2:
7 5
7 8
8 4
Test case 3:
4 4
#include<stdio.h>
struct point{ int x, y; };
point  a[10000];
void copy(point &k, point& i){
	k.x = i.x;
	k.y = i.y;
}
bool less(point i, point j){
	if (i.x < j.x)return true;
	if (i.x==j.x&&i.y < j.y)return true;
	return false;
}
bool big(point i, point j){
	if (i.x>j.x)return true;
	if (i.x==j.x&&i.y>j.y)return true;
	return false;
}
void sort(int from, int to){
	if (from >= to)return;
	int i = from, j = to;
	point k;
	copy(k, a[from]);
	while (1){
		while (big(a[j], k))j--;
		if (j == i)break;
		copy(a[i], a[j]);
		copy(a[j], k);
		i++;
		while (less(a[i], k))i++;
		if (j == i)break;
		copy(a[j], a[i]);
		copy(a[i], k);
		j--;
	}
	sort(from, i - 1);
	sort(i + 1, to);
}
int main(){
	freopen("in.txt", "r", stdin);
	int t;
	scanf("%d", &t);
	int tt;
	for(tt=1;tt<=t;tt++){
		int n;
		scanf("%d", &n);
		int i;
		for (i = 0; i < n; i++)scanf("%d%d",&a[i].x,&a[i].y);
		sort(0, n - 1);
		printf("Test case %d:
", tt);
		for (i = 0; i < n; i++)
			printf("%d %d
", a[i].x, a[i].y);
	}
	return 0;
}