题解 P1183 【多边形的面积】

2018-07-10 14:46:34


数论看了头晕的看这里

dalao们用的是数学,来一发纯模拟的: 先贴一发40分代码(连样例都过不了的):

#include <bits/stdc++.h>
using namespace std;
int n;int a[505][505];
int t1,t2,t3,t4,dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
struct Node{int x,y;};
queue<Node> q; 
void bfs(int x,int y,int clr) //bfs填充
{
    while (!q.empty()) q.pop();
    q.push({x,y});
    while (!q.empty())
    {
        Node nd = q.front();q.pop();
        if (a[nd.x][nd.y]) continue;
        a[nd.x][nd.y] = clr;
        for (int i = 0;i < 4;i++)
        {
            int nx = nd.x + dx[i],ny = nd.y + dy[i];
            if (nx >= 0 && nx <= 500 && ny >= 0 && ny <= 500) q.push({nx,ny}); //扩展
        }
    }
} 
int main ()
{
    scanf("%d",&n);
    int sx = 0,sy = 0;
    for (int i = 0;i <= n;i++) //为封口,多做一轮
    {
        if (i != n) scanf("%d%d",&t1,&t2); else t1 = sx,t2 = sy;//else的一步用来封口
        t1 += 250;t2 += 250;
        //t1,t2:新读进来的;t3,t4:上一步的
        if (i)
        {
            if (t1 == t3)
            {
                int mv = min(t2,t4),mx = t2 + t4 - mv;//新的坐标和旧的坐标之间连线,mv为坐标较小的,mx为坐标较大的,下同
                for (int i = mv;i <= mx;i++) a[t1][i] = 1;
            }
            else
            {
                int mv = min(t1,t3),mx = t1 + t3 - mv;
                for (int i = mv;i <= mx;i++) a[i][t2] = 1;
            }
        } 
        else
        {
            sx = t1 - 250;sy = t2 - 250;
            //只读了一个点
        }
        t3 = t1;t4 = t2;//更新旧值
    }

    bfs(0,0,-1);//填充外面的,用-1表示
    for (int i = 0;i <= 500;i++)
        for (int j = 0;j <= 500;j++)
            if (a[i][j] == 0) bfs(i,j,1);//填充里面的,用1表示
    int ans = 0;
    for (int i = 0;i <= 500;i++)
        for (int j = 0;j <= 500;j++)
            if (a[i][j] == 1 && a[i + 1][j] == 1 
                && a[i][j + 1] == 1 && a[i + 1][j + 1] == 1) ++ans;//每当有2*2的一个全部由1组成的正方形出现时,面积就加1(四个1对应四个点)
    printf("%d\n",ans);
    return 0;
}

算法思路:将多边形的线勾出来,然后再算面积。比如对于矩阵

1 1 1 0

1 1 1 1

1 1 1 1

1 1 1 0

一个数字对应一个顶点,图中的图形的面积为3*3-2=7

代码的缺陷是:一些凹进去的东西会算上去:

比如

1 1 1 1

1 1 1 1

1 1 1 1

定义第x行第y列的点为(x,y),假设题目中是(1,2)到(2,2)中有一条线,(2,2)到(3,2)是一条线,

(3,2)到(3,1)有一条线,则绘图效果和上面那个矩阵一样:凹进去的部分被“填补了”

解决方案为:将矩阵长宽各扩大2倍,勾线时也按原来的2倍画,最后算面积时➗4。

正解代码(相同部分的注释就不写啦):

#include <bits/stdc++.h>
using namespace std;
int n;int a[2005][2005];
int t1,t2,t3,t4,dx[] = {1,0,-1,0},dy[] = {0,1,0,-1},lx = 1001,ly = 1001,
    rx = -1,ry = -1;
struct Node{int x,y;};
queue<Node> q; 
void bfs(int x,int y,int clr) 
{
    while (!q.empty()) q.pop();
    q.push({x,y});
    while (!q.empty())
    {
        Node nd = q.front();q.pop();
        if (a[nd.x][nd.y]) continue;
        a[nd.x][nd.y] = clr;
        for (int i = 0;i < 4;i++)
        {
            int nx = nd.x + dx[i],ny = nd.y + dy[i];
            if (nx >= lx && nx <= rx && ny >= ly && ny <= ry) q.push({nx,ny});
        }
    }
}
int main ()
{
    scanf("%d",&n);
    int sx = 0,sy = 0,ssx,ssy;
    scanf("%d%d",&sx,&sy);sx += 1001;sy += 1001;a[sx][sy] = 1;t3 = sx;t4 = sy;
    ssx = sx;ssy = sy;//sx,sy表示当前勾线位置
    //ssx,ssy表示第一个点
    lx = min(lx,ssx);ly = min(ly,ssy);rx = max(rx,ssx);ry = max(ry,ssy);
    //lx,ly左上角坐标,rx,ry右下角坐标,是一个优化
    for (int i = 1;i <= n;i++)
    {
        if (i != n)
        {
            scanf("%d%d",&t1,&t2);t1 += 1001;t2 += 1001;//加1000刚好会RE,悲哀,我在这个地方卡了半个小时
        }
        else t1 = ssx,t2 = ssy;
        if (t1 == t3)
        {
            int dis = 2 * abs(t2 - t4);//距离,下同
            if (t2 < t4)
            {
                for (int i = 1;i <= dis;i++) a[sx][++sy] = 1;
            }
            else
            {
                for (int i = 1;i <= dis;i++) a[sx][--sy] = 1;
            }
        }
        else
        {
            int dis = 2 * abs(t1 - t3);
            if (t1 < t3)
            {
                for (int i = 1;i <= dis;i++) a[++sx][sy] = 1;
            }
            else
            {
                for (int i = 1;i <= dis;i++) a[--sx][sy] = 1;
            }
        }

        t3 = t1;t4 = t2;
        lx = min(lx,sx);ly = min(ly,sy);rx = max(rx,sx);ry = max(ry,sy);//更新左上角,右下角
    }
    lx--;rx++;ly--;ry++;//将外面一圈连起来
    bfs(lx,ly,-1);
    for (int i = lx;i <= rx;i++)
        for (int j = ly;j <= ry;j++)
            if (a[i][j] == 0)
            {
                bfs(i,j,1);break; 
            } 
    int ans = 0;
    for (int i = lx;i <= rx;i++)
        for (int j = ly;j <= ry;j++)
            if (a[i][j] == 1 && a[i + 1][j] == 1 
                && a[i][j + 1] == 1 && a[i + 1][j + 1] == 1) ++ans;
    printf("%d\n",ans / 4);
    return 0;
}