题目链接：uva 10574 - Counting Rectangles
题目大意：给出n个点，问选出4个点作为定点，能够组成多少个平行与坐标轴的矩形。
解题思路：首先将点依照x排序(优化)，然后处理出全部平行于y轴的线段。记录这些线段的y1和y2，接着仅仅要找出y1和y2值均相等的边，C(2cnt).
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int N = 5005; struct point { int x, y; void get () { scanf("%d%d", &x, &y); } void set (int x, int y) { this->x = x; this->y = y; } }p[N], l[N*N/2]; int n, m; inline bool cmp(const point& a, const point& b) { if (a.x != b.x) return a.x < b.x; return a.y < b.y; } void init () { scanf("%d", &n); for (int i = 0; i < n; i++) p[i].get(); sort(p, p + n, cmp); m = 0; for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { if (p[i].x != p[j].x) break; l[m++].set(p[i].y, p[j].y); } } sort(l, l + m, cmp); } ll solve () { ll ans = 0; for (int i = 0; i < m;) { int mv = i+1; while (l[i].x == l[mv].x && l[i].y == l[mv].y) mv++; ll c = mv - i; if (c >= 2) ans += c * (c - 1) / 2; i = mv; } return ans; } int main () { int cas; scanf("%d", &cas); for (int i = 1; i <= cas; i++) { init(); printf("Case %d: %lld\n", i, solve()); } return 0; }转载于:https://www.cnblogs.com/bhlsheji/p/5168527.html
相关资源：数据结构—成绩单生成器