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