广场舞 蓝桥真题

本文主要是介绍广场舞 蓝桥真题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://www.dotcpp.com/oj/problem1838.html

50%数据参考博客https://blog.csdn.net/qq_39562286/article/details/80033097

很多博客的思路都是 枚举每个小正方形的右上角 然后判断其余三个角是不是在多边形内 但是当出现斜率不存在的直线时就不好使了 比如下面这个样例

6
0 0
2 0
2 3
1 3
1 1
0 3

本应输出4 按上述方法却得6 所以除非保证所有直线斜率全都存在 否则不可行

 

正解就很巧妙得避开这个问题 对每一列正方形（假设只有连续的一段）一定有两条直线封住上下底 n^2的暴力枚举即可

还有就是ceil与floor的使用 mark

 

 

#include <bits/stdc++.h>
using namespace std;
const double N=1000000000000000000.0;
const int maxn=1e3+10;struct node1
{int x,y;
};struct node2
{node1 p1,p2;
};struct node3
{double yl,yr;
};node1 point[maxn];
node2 line[maxn];
node3 pre[maxn];
int n;double gety(double x,node2 l)
{double y,x1,y1,x2,y2;x1=l.p1.x,y1=l.p1.y,x2=l.p2.x,y2=l.p2.y;y=(y2-y1)*(x-x1)/(x2-x1)+y1;return y;
}bool cmp(node3 n1,node3 n2)
{return n1.yl<n2.yl;
}int solve()
{int res,cnt,minn,maxx,l,r,i,j;minn=1000,maxx=-1000;for(i=0;i<n;i++){minn=min(minn,point[i].x),maxx=max(maxx,point[i].x);}res=0;for(i=minn+1;i<=maxx;i++){cnt=0;for(j=0;j<n;j++){l=line[j].p1.x,r=line[j].p2.x;if(l<=i-1&&i<=r){pre[cnt].yl=gety(i-1,line[j]),pre[cnt].yr=gety(i,line[j]);cnt++;}}sort(pre,pre+cnt,cmp);for(j=0;j<cnt/2;j++){l=int(ceil(max(pre[2*j].yl,pre[2*j].yr)));r=int(floor(min(pre[2*j+1].yl,pre[2*j+1].yr)));if(l<r) res+=(r-l);}}return res;
}int main()
{int i,ans;scanf("%d",&n);for(i=0;i<n;i++){scanf("%d%d",&point[i].x,&point[i].y);}for(i=0;i<n;i++){line[i].p1=point[i],line[i].p2=point[(i+1)%n];if(line[i].p1.x>line[i].p2.x){swap(line[i].p1,line[i].p2);}}printf("%d\n",solve());return 0;
}

 

这篇关于广场舞 蓝桥真题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---