| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
水过,附代妈//============================================================================
// 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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator