【Luogu2867】大广场Big Square

来源和评测点

USACO06 NOV
Luogu2867

题目

【题目大意】
农民 John 的牛参加了一次和农民 Bob 的牛的竞赛。
他们在区域中画了一个N乘N 的正方形点阵,两个农场的牛各自占据了一些点。
当然不能有两头牛处于同一个点。
农场的目标是用自己的牛作为4个顶点,
形成一个面积最大的正方形(不必须和边界平行) 。
除了 Bessie 以外,FJ其他的牛都已经放到点阵中去了,
要确定bessie放在哪个位置,
能使得农民约翰的农场得到一个最大的正方形
(Bessie不是必须参与作为正方形的四个顶点之一)。
【输入格式】
第一行是N
接下来是一个N乘N的矩阵,
字符解释:
‘J’ John 的牛,
‘B’ Bob 的牛,
‘*‘ 空点。
数据保证至少一个空点
【输出格式】
面积,如果没有就输出0
【输入样例】
6
J*J***
******
J***J*
******
**B***
******
【输出样例】
4

分析

随便用暴力做,居然过了……
难点就是已知对角线上两个点求出正方形另外两个点

膜师兄时大概用了高中向量的知识,但也挺好理解的,
就是“固定方向固定距离”?

假如有两个点$(a,b)和(c,d)$,把他们作为对角线
先计算出中点$(mx=\frac{a+c}{2},my=\frac{b+d}{2})$
计算出两点间向量
$(fx=\frac{a-c}{2},fy=\frac{b-d}{2})$
向量反转,另外两点分别为
$(qx=mx+(-fy),qy=my+(fx))和(mx+(fy),my+(-fx))$
面积则是
$( \sqrt{ (a-qx)^2+(b-qy)^2 })^2=(a-qx)^2+(b-qy)^2$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int mymax(int x,int y) {return x>y?x:y;}
const int MAXN=150;
struct nod
{
int x,y;
}p[MAXN*MAXN];//已经使用的点
int ptn=0;//数量
int mp[MAXN][MAXN];
int n;
//判断x是不是整数y,我随便打的。。不是很严谨
bool dint(double x,int y)
{
double ty=y;
return ty-0.001<=x and x<=ty+0.001;//在大致区间内
}
int ans=0;
void solve()
{
for(int i=1;i<=ptn;i++)
{
for(int j=1;j<=i-1;j++)//枚举互为对角线的点
{
double a=p[i].x,b=p[i].y;//点1
double c=p[j].x,d=p[j].y;//点2
double mx=(a+c)/2.0,my=(b+d)/2.0;//中点
double fx=(a-c)/2.0,fy=(b-d)/2.0;//向量
double qx=mx+(-fy),qy=my+(fx);
if(qx<1 or qx>n) continue;if(qy<1 or qy>n) continue;
double wx=mx+(fy),wy=my+(-fx);
if(wx<1 or wx>n) continue;if(wy<1 or wy>n) continue;
//理论做法:取中间向量,并应用在中点上
//由于初三还没正式学向量,不严谨
if(qx==wx and qy==wy) continue;
int ax=int(qx+0.5),ay=int(qy+0.5);//注意四舍五入
int bx=int(wx+0.5),by=int(wy+0.5);
if(!dint(qx,ax)) continue;//不是整点
if(!dint(qy,ay)) continue;//不是整点
if(!dint(wx,bx)) continue;//不是整点
if(!dint(wy,by)) continue;//不是整点
int qm=mp[ax][ay],wm=mp[bx][by];//状态
if(qm==1 or wm==1) continue;//被占用
if(qm==0 and wm==0) continue;//贝西只有一个……
double sq=(a-qx)*(a-qx)+(b-qy)*(b-qy);//面积
ans=mymax(sq,ans);
}
}
}
char s[MAXN];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",s+1);
for(int j=1;j<=n;j++)
{
if(s[j]=='*') mp[i][j]=0;
if(s[j]=='B') mp[i][j]=1;
if(s[j]=='J')
{
ptn++;
p[ptn].x=i;p[ptn].y=j;
mp[i][j]=2;
}
}
}
solve();
printf("%d",ans);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2017-12/大广场.html
转载请注明出处,谢谢!

给我投食吧,您的支持将鼓励我继续创作!