本文共 2075 字，大约阅读时间需要 6 分钟。

魔法阵

时间限制: 1 Sec 内存限制: 128 MB [提交] [状态] 题目描述 为了增加菜地产量，小X的妹妹魔法师小L决定对菜地使用魔法。 小X家的菜地可以看作是一个N*N的网格，在其中的一些格点上，存在着一些魔法阵眼和稻草人（每个格点最多只会有一个魔法阵眼或一个稻草人，且已有的魔法阵眼不会在稻草人上）。当有四个魔法阵眼恰好能构成一个正方形时（这个正方形的四边不用与菜地平行），小L就能启动一个以这四个魔法阵眼为顶点的正方形魔法阵。 由于法力有限，小L最多只能在菜地里再添加一个魔法阵眼（当然该魔法阵眼不能添加在稻草人上），最多只能启动一个魔法阵。她希望这个魔法阵的面积尽可能大。请计算出最大的可能的魔法阵面积。

输入

第1行一个正整数N，其意义如题目描述中所述。 第2行两个正整数M,Q，分别表示已有魔法阵眼和稻草人的数量。 接下来M行每行两个正整数X,Y，表示一个魔法阵眼的坐标。 接下来Q行每行两个正整数X,Y，表示一个稻草人的坐标。

输出

一行一个整数表示最大的可能的魔法阵面积。 样例输入 Copy 6 4 1 1 1 1 3 3 1 3 5 5 3 样例输出 Copy 4 提示

红点为已有的魔法阵眼，蓝点为稻草人，绿点为小L添加的魔法阵眼，阴影部分为魔法阵，大小为4。

【数据范围】 对于30%的数据，N,M,Q < 10 对于60%的数据，N,M,Q < 200 对于100%的数据，N,M,Q < 2000，1 < X,Y < N

题意就是添加一个点，让后算出加完点之后，最大的正方形面积。比较明显的是枚举两个红点当作对角线，让后根据这两个点来算出另外两个点的坐标，具体公式如下：

int x1=a[i].x,x2=a[j].x;			int y1=a[i].y,y2=a[j].y;						int midx=x1+x2>>1,midy=y1+y2>>1;			int x3=midx-(midy-y1),x4=midx+(midy-y1);			int y3=midy+(midx-x1),y4=midy-(midx-x1);

具体证明：(本人画图太水)

让后直接套公式进去算出结果即可，还要注意下因为我们这里是 int 来存的 mid ，为了避免奇数算出来的 mid 是小数，我们可以把每个点坐标乘2 ，让后最终答案结果除4即可。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
      
     
    
   

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/105632610 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！