poj-3739. Special Squares(二维前缀和)

时间：2023-03-08 22:32:48

题目链接：

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

Output one line containing an integer specifies the number of special squares. The test data ensures that the result is less than 2^31

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;

}

　　

相关文章