题目链接：
I. Special Squares
There are some points and lines parellel to x-axis or y-axis on the plane. If arbitrary chosen two lines parallel to x-axis and two lines parallel to y-axis, one rectangle, or sometimes a square, will be formed. If a square is formed and there is one or more point in the square or on the side of the square, the square is called a "special square". Please find the number of special squares.
Input
The 1st line contains three positive integer n1, n2 and n3. n1 stands for the number of lines parallel to x-axis, n2 stands for the number of lines parallel to y-axis, n3 stands for the number of points.(0<n1, n2, n3≤1000)Each of the 2nd line to (n1+1)th line gives an integer y_i (0≤y_i≤1000), means a line with equation y=y_i.Each of the (n1+2)th line to (n1+n2+1)th line gives an integer x_j (0≤x_j≤1000), means a line with equation x=x_j.Each of the last three lines gives two integers px_k and py_k (0≤px_k,py_k≤1000), means a point with coordinate (px_k, py_k).
Output
Sample Input
4 4 3
0 2 4 6
0 2 4 6
1 1
3 3
6 6
Sample Output
8 题意： 给出一些x和y方向上的直线,然后让分别选两个会形成长方形,其中是正方形且在其内部和边界上有给出的点时叫这种正方形,问有多少个这种正方形; 思路： 把给出的点求出一个二维前缀和,然后枚举一个方向上的两个,在枚举另一个方向上的一条线,这就得到了这个正方形,然后用前缀和判断是否存在点,复杂度是O(n*n*n)数据范围给的有问题,我开大了一倍才过;
题解说枚举对角线,然后枚举坐下角,这样复杂度是O(n*n),想不通为啥是这个复杂度; AC代码：
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
//#include <bits/stdc++.h>
#include <stack>
#include <map> using namespace std; #define For(i,j,n) for(int i=j;i<=n;i++)
#define mst(ss,b) memset(ss,b,sizeof(ss)); //typedef long long LL;
typedef unsigned long long LL;
template<class T> void read(T&num) {
char CH; bool F=false;
for(CH=getchar();CH<'0'||CH>'9';F= CH=='-',CH=getchar());
for(num=0;CH>='0'&&CH<='9';num=num*10+CH-'0',CH=getchar());
F && (num=-num);
}
int stk[70], tp;
template<class T> inline void print(T p) {
if(!p) { puts("0"); return; }
while(p) stk[++ tp] = p%10, p/=10;
while(tp) putchar(stk[tp--] + '0');
putchar('\n');
} const LL mod=1e9+7;
const double PI=acos(-1.0);
const int inf=1e9;
const int N=1e3+20;
const int maxn=2e3+20;
const double eps=1e-3; int sum[maxn][maxn],su[maxn][maxn],n1,n2,n3;
int x[maxn],y[maxn],vis[2*maxn],a[maxn][maxn];
int main()
{
mst(a,0);
mst(vis,0);
read(n1);read(n2);read(n3);
for(int i=1;i<=n1;i++)read(y[i]),y[i]++;
for(int i=1;i<=n2;i++)read(x[i]),x[i]++,vis[x[i]]=1;
sort(y+1,y+n1+1);sort(x+1,x+n2+1);
int fx,fy;
for(int i=1;i<=n3;i++)
{
read(fx);read(fy);
fx++;fy++;
a[fx][fy]=1;
}
for(int i=1;i<N;i++)
for(int j=1;j<N;j++)
su[i][j]=su[i][j-1]+a[i][j];
for(int i=1;i<N;i++)
for(int j=1;j<N;j++)
sum[i][j]=sum[i-1][j]+su[i][j];
int ans=0,dx,dy,ux,uy;
for(int i=1;i<=n1;i++)
{
for(int j=i+1;j<=n1;j++)
{
int l=y[j]-y[i];
for(int k=1;k<=n2;k++)
{
if(x[k]+l>=N||x[k]+l<=0)continue;
else if(!vis[x[k]+l])continue;
else
{
dx=x[k];dy=y[i];
ux=x[k]+l;uy=y[j];
if(sum[ux][uy]+sum[dx-1][dy-1]-sum[ux][dy-1]-sum[dx-1][uy]>0)ans++;
}
}
}
}
printf("%d\n",ans);
return 0;
}