题解 P1183 【多边形的面积】

~~数论看了头晕的看这里~~ dalao们用的是数学，来一发纯模拟的： 先贴一发40分代码（连样例都过不了的）: ```cpp #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。 正解代码(相同部分的注释就不写啦): ```cpp #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; } ```