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

水过,附代妈

Posted by KatrineYang at 2016-06-29 14:07:07 on Problem 2002
//============================================================================
// Name        : main2002.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;

class pt{
	public:
	int x;
	int y;
	pt(int X, int Y): x(X), y(Y){}
	pt(): x(0), y(0){}
};

bool operator<(pt& p1, pt& p2){
	if(p1.x < p2.x) return true;
	if(p1.x > p2.x) return false;
	return p1.y < p2.y;
}

bool operator>(pt& p1, pt& p2){
	if(p1.x < p2.x) return false;
	if(p1.x > p2.x) return true;
	return p1.y > p2.y;
}

bool operator==(pt& p1, pt& p2){
	return p1.x==p2.x && p1.y==p2.y;
}

pt pts[1000];

int np;

int partion(pt *array, int p, int r) {
		pt x = array[r];
		int i = p - 1;//注意这点,把i设成负值,然后作为移动的标志
		int j;
		for (j = p; j < r; j++) {
			if (array[j] < x) {
				i++;
				pt temp = array[j];
				array[j] = array[i];
				array[i] = temp;
			}
		}
		pt temp = array[j];
		array[j] = array[i + 1];
		array[i + 1] = temp;
		return i+1;//返回的应该是交换后的哨兵的位置
}
		//递归解决每个划分后的小
void quickSort(pt *array, int p, int r) {
		if (p < r) {
			int q = partion(array, p, r);
			quickSort(array, p, q - 1);
			quickSort(array, q + 1, r);
		}
}

bool bS(pt tar, int start, int end){
	if(end < start) return false;
	if(end - start <= 1){
		return tar == pts[start] || tar == pts[end];
	}
	int middle = (start + end)/2;
	if(tar == pts[middle]) return true;
	else if(tar < pts[middle]){
		return bS(tar, start, middle-1);
	}
	else{
		return bS(tar, middle+1, end);
	}
}

int main() {
	while(1){
		cin >> np;
		if(!np) return 0;
		for(int i = 0; i < np; i++){
			cin >> pts[i].x >> pts[i].y;
		}
		quickSort(pts, 0, np-1);
		int cnt = 0;
		if(np < 4){
			cout << 0 << endl;
			continue;
		}
		for(int i = 0; i <= np-4; i++){
			for(int j = i+1; j < np; j++){
				if(pts[j].x <= pts[i].x || pts[j].y > pts[i].y){
					continue;
				}
				int a = pts[i].x, b = pts[i].y, c = pts[j].x, d = pts[j].y;
				pt p3(a+b-d, b+c-a), p4(b+c-d, c+d-a);
				if(bS(p3, i+1, np-1) && bS(p4, i+1, np-1)){
					cnt++;
				}
			}
		}
		cout << cnt << endl;
	}
	//cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!
	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