生活随笔
收集整理的這篇文章主要介紹了
HDU 5128 The E-pang Palace
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
//去他媽的枚舉，還是計算幾何靠譜，暴力方便！！！！！！
//強烈建議比賽時候用計算幾何暴力判斷合法性
1 //去他媽的枚舉，還是計算幾何靠譜，暴力方便！！！！！！
2 //強烈建議比賽時候用計算幾何暴力判斷合法性
3 #include <iostream>
4 #include <cstring>
5 #include <algorithm>
6 #include <cstdio>
7 using namespace std;
8 int x[
40],y[
40];
9 int N;
10 bool p[
222][
222];
11 struct node
12 {
13 int x,y;
14 int id;
15 int t;
16 }E[
5];
17 int ans =
0;
18 bool cmp1(node a,node b)
19 {
20 return a.x <
b.x;
21 }
22 bool cmp2(node a,node b)
23 {
24 return a.y <
b.y;
25 }
26 void solve(
int a,
int b,
int c,
int d)
27 {
28 int flx =
1,fly=
1;
29 int fx=
1,fy=
1;
30 int ft1=
0,ft2=
0;
31 int l1,l2;
32 E[
1].id = a;E[
2].id=b;E[
3].id = c;E[
4].id=
d;
33 E[
1].t=
1;E[
2].t=
1;E[
3].t=
2;E[
4].t=
2;
34 for (
int i =
1; i<=
4; i++
)
35 E[i].x=x[E[i].id],E[i].y =
y[E[i].id];
36 if ((!p[E[
1].x][E[
2].y])|| (!p[E[
2].x][E[
1].y])||(!p[E[
3].x][E[
4].y])||(!p[E[
4].x][E[
3].y]))
return;
// 構成矩形
37
38 for (
int i =
1;i<=
4;i++
)
39 for (
int j = i+
1; j<=
4;j++
)
40 {
41 if (E[i].x == E[j].x) fx=
0;
42 if (E[i].y == E[j].y) fy=
0;
43 }
44
45 sort(E+
1,E+
5,cmp1);
46 if (E[
1].t!=E[
2].t) flx =
0;
47 if (E[
1].t==E[
4].t) ft1 = E[
1].t;
48 if (flx*fx ==
1)
// flx 和 fx 都等于1必然有解
49 {
50 l1 = abs((E[
1].x-E[
2].x)*(E[
1].y-E[
2].y));
51 l2 = abs((E[
3].x-E[
4].x)*(E[
3].y-E[
4].y));
52 if (l1*l2!=
0) ans = max(ans,l1+
l2);
53 return;
54 }
55 sort(E+
1,E+
5,cmp2);
56 if (E[
1].t!=E[
2].t) fly =
0;
57 if (E[
1].t==E[
4].t) ft2 = E[
1].t;
58 if (fly*fy ==
1)
// fly 和 fy 都等于1必然有解
59 {
60 l1 = abs((E[
1].x-E[
2].x)*(E[
1].y-E[
2].y));
61 l2 = abs((E[
3].x-E[
4].x)*(E[
3].y-E[
4].y));
62 if (l1*l2!=
0) ans = max(ans,l1+
l2);
63 return;
64 }
65 if (ft2==ft1 && ft2!=
0)
// 被包含在里面
66 {
67 if (fx*fy==
0)
return;
// 包含情況不能相交
68 ans = max(abs((E[
1].x-E[
4].x)*(E[
1].y-E[
4].y)),ans);
69 return;
70 }
71 return;
72 }
73 int main()
74 {
75 while (cin>>N &&
N)
76 {
77 memset(p,
false,
sizeof(p));
78 for (
int i =
1; i<=N; i++
)
79 {
80 scanf(
"%d%d",&x[i],&
y[i]);
81 p[x[i]][y[i]] =
true;
82 }
83 ans = -
1;
84 for (
int a =
1; a <=N;a++
)
85 for (
int b =
1; b <=N;b++
)
86 for (
int c =
1; c <=N;c++
)
87 for (
int d =
1; d <=N;d++
)
88 {
89 if (a==b||b==c||c==d||a==c||b==d||a==d)
continue;
90 solve(a,b,c,d);
91 }
92 if (ans==-
1) puts(
"imp");
93 else cout <<ans <<
endl;
94 }
95 }
日狗的代碼，提供對拍，別看了，丑的一逼 ?
轉載于:https://www.cnblogs.com/HITLJR/p/6602067.html
總結
以上是生活随笔為你收集整理的HDU 5128 The E-pang Palace的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
