题目地址： http://poj.org/problem?id=1314
题意： 给出一串的点，有些点可以构成正方形，请按照字符排序输出。
因为这道题的用处很大， 最近接触的cv 中的Rectangle Detection 中就有方法使用到了这个算法。 但实际中使用的算法还是暴力。
不过因为数据点较少，可以直接快排之后，再来个迭代，就得到答案了
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 30; struct Node{
string label;
int x,y;
}nd[maxn]; int n; int cmp(const void *a, const void *b){
Node* aa = (Node *)a;
Node* bb = (Node *)b;
if(aa->x == bb->x){
return aa->y - bb->y;
}else{
return aa->x - bb->x;
}
} int main(){
freopen("in.txt", "r", stdin); int i,j,k, l, cnt = 1;
char word[4];
while( cin>>n && n!=0){
for(i=0; i<n; i++){
cin>>nd[i].label>>nd[i].x>>nd[i].y;
}
qsort(nd, n, sizeof(nd[0]), cmp);
vector<string> vt;
for(i=0; i<n; i++){
for(j=i+1; j<n && nd[j].x == nd[i].x; j++){
for(k=j+1; k<n; k++){
if(nd[k].y == nd[i].y){
for(l=k+1; l<n && nd[l].x == nd[k].x; l++){
if(nd[l].y == nd[j].y){
string tmp = "";
tmp += nd[j].label; tmp += nd[l].label;
tmp += nd[k].label; tmp += nd[i].label;
vt.push_back(tmp);
}
}
}
}
}
}
if(vt.size() == 0){
printf("Point set %d: No rectangles\n", cnt++);
}else{
printf("Point set %d:\n", cnt++);
sort(vt.begin(), vt.end());
for(i=0; i<vt.size(); i++){
if((i+1)%10 == 0){
cout<<" "<<vt[i]<<endl;
}else{
cout<<" "<<vt[i];
}
}
if(i%10 != 0){
printf("\n");
}
}
}
return 0;
}