HDU 4739 求正方形个数

九野的博客,转载请注明出处:http://blog.csdn.net/acmmmm/article/details/11711707

求所有可能围成的正方形,借个代码

#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <cstdio>
#include <math.h>
#include <cstdlib>
#include <string.h>
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
#define LL long long
#define PI acos(-1.0)
#define FRE freopen("c:\\users\\nitlian\\desktop\\input.txt","r",stdin)
#define FF freopen("c:\\users\\nitlian\\desktop\\output.txt", "w", stdout)
#define N 5100
#define M 1148576
#define inf 1000000000 struct node {
int a, b, c, d;
void set (int _a, int _b, int _c, int _d) {
a = _a; b = _b; c = _c; d = _d;
}
}pe[N];
struct point {
int x, y;
void set () {
scanf ("%d%d", &x, &y);
}
}p[30];
int cnt;
int cmp (point a, point b) {
if (a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
int dp[M];
int dfs (int s) {
if (dp[s] != -1) return dp[s];
int Max = 0;
for (int i = 0; i < cnt; ++i) {
if ((s&(1<<pe[i].a)) + (s&(1<<pe[i].b))+(s&(1<<pe[i].c)) + (s&(1<<pe[i].d)) == 0) {
int si = s + (1<<pe[i].a) + (1<<pe[i].b) + (1<<pe[i].c) + (1<<pe[i].d);
Max = max (Max, dfs (si) + 4);
}
}
return dp[s]= Max;
}
int main () {
int n;
while (scanf ("%d", &n), n != -1) {
for (int i = 0; i < n; ++i) {
p[i].set();
}
cnt = 0;
sort (p, p + n, cmp);
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (p[i].x != p[j].x) break;
for (int ii = j + 1; ii < n; ++ii) {
for (int jj = ii + 1; jj < n; ++jj) {
if (p[ii].x != p[jj].x) continue;
if (p[i].y == p[ii].y && p[j].y == p[jj].y && p[j].y - p[i].y == p[ii].x - p[i].x) {
pe[cnt].set (i, j, ii, jj);
// cout << i << ' ' << j << ' ' << ii << ' ' << jj << endl;
cnt++;
}
}
}
}
}
memset (dp, -1, sizeof (dp));
printf ("%d\n", dfs (0));
}
}
上一篇:noi题库(noi.openjudge.cn) 1.7编程基础之字符串T31——T35


下一篇:LINUX下的时间与时区的设置