蓝桥杯广场舞

题目描述

LQ 市的市民广场是一个多边形，广场上铺满了大理石的地板砖。

地板砖铺得方方正正，就像坐标轴纸一样。

以某四块砖相接的点为原点，地板砖的两条边为两个正方向，一块砖的边长为横纵坐标的单位长度，则所有横纵坐标都为整数的点都是四块砖的交点（如果在广场内）。

广场的砖单调无趣，却给跳广场舞的市民们提供了绝佳的参照物。每天傍晚，都会有大批市民前来跳舞。

舞者每次都会选一块完整的砖来跳舞，两个人不会选择同一块砖，如果一块砖在广场边上导致缺角或者边不完整，则没人会选这块砖。（广场形状的例子参考下图）

现在，告诉你广场的形状，请帮 LQ 市的市长计算一下，同一时刻最多有多少市民可以在广场跳舞。

输入描述

输入的第一行包含一个整数 nn，表示广场是 nn 边形的（因此有 nn 个顶点）。

接下来 nn 行，每行两个整数，依次表示 nn 边形每个顶点的坐标（也就是说广场边缘拐弯的地方都在砖的顶角上。数据保证广场是一个简单多边形。

其中，nn 不超过 1000，横纵坐标的绝对值均不超过 10^8108。

输出描述

输出一个整数，表示最多有多少市民可以在广场跳舞。

输入输出样例

示例

输入

输出

样例说明

广场题干图中所示，一共有 7 块完整的地板砖，因此最多能有 7 位市民一起跳舞。

运行限制

最大运行时间：1s
最大运行内存: 256M

题意

LQ 市的市民广场是一个多边形，广场上铺满了大理石的地板砖。

地板砖铺得方方正正，就像坐标轴纸一样。

广场的砖单调无趣，却给跳广场舞的市民们提供了绝佳的参照物。每天傍晚，都会有大批市民前来跳舞。

现在，告诉你广场的形状，请帮 LQ 市的市长计算一下，同一时刻最多有多少市民可以在广场跳舞。

输入

输入的第一行包含一个整数 nn，表示广场是 nn 边形的（因此有 nn 个顶点）。

接下来 nn 行，每行两个整数，依次表示 nn 边形每个顶点的坐标（也就是说广场边缘拐弯的地方都在砖的顶角上。数据保证广场是一个简单多边形。

数据规模如下：

对于 30%的数据，nn 不超过 100100，横纵坐标的绝对值均不超过 100100。
对于 50%的数据，nn 不超过 10001000，横纵坐标的绝对值均不超过 10001000。
对于 100%的数据，nn 不超过 10001000，横纵坐标的绝对值均不超过 10^8108（一亿）。

输出

输出一个整数，表示最多有多少市民可以在广场跳舞。

分析

本题是一道明显的计算几何的题目，简单来说题意是：求所给的多边形（任意多边形）内部有多少个完整的小正方形。同时我们注意到，多边形的顶点是按顺序(顺时针顺序或者逆时针顺序)依次给出的，这样我们在后面构造线段和该多边形时较为方便，首尾依次连接即可。

读题之后，首先我们可以想到，要先找到这个多边形的边界坐标，即找到多边形最大最小的横纵坐标，就相当于根据最大最小横纵坐标构造一个大正方形框住这个多边形，我们在这个大正方形内进行求解即可。

我们在计算整个多边形内的小正方形数目时，首先可以想到：如果我们将整个多边形使用若干条直线 x=ix=i,将其分成宽为 1 的若干长条，然后我们分别计算每个长条中有多少小正方形，最后求和便是答案。

这时我们来思考怎么计算一个长条中有多少个小正方形：假设我们计算 x=i-1x=i−1 和 x=ix=i 所围成的长条。很明显，这个长条的上下边为原多边形的边。那么我们分别计算 x=i-1x=i−1 和 x=ix=i与下边交点的纵坐标，分别向上取整后取最大值 y_1y1。然后再计算x=i-1x=i−1 和 x=ix=i与下边交点的纵坐标，分别向下取整后取最小值 y_2y2。那么显而易见，小正方形的数量为 y_2-y_1y2−y1。如下图所示：

但是我们还有两个点需要注意：

下图中的多边形，在分成长条时，红色部分出现了一个长条中包含了多边形的几部分，且背分隔开，此时，我们就需要记录多边形与 x=ix=i 产生交点的每条边，并且记录对应的交点纵坐标，然后按纵坐标升序排列，相邻的两两组合，形成若干小长条即可。

可能有两条线与 x = ix=i 这条线交于一点（i，y）在排序的时候有可能导致这两条线的位置互换，从而得出错误答案。那么，我们记录线在 x = i-0.5x=i−0.5 处的纵坐标，这样纵坐标就不会重复了（纵坐标的值关系到线的位置）。

总体上，我们找到了一个时间复杂度为 O(n^2)O(n2) 的解，可以通过 50% 的数据。

解法

定义点、线结构体，录入点（输入为有序输入，顺时针或者逆时针），然后两点构成一条线，nn 个点 nn 条线。
算出最左、最右的横坐标值 minx，maxx。
当 x = minx+1 :

（1）遍历每一条线，如果这条线与 x = minx+1 这条线有交点，就把交点处的纵坐标算出，并用一个数组 ans 记录这条线还有纵坐标.

（2）对 ans 数组进行排序，以记录的纵坐标的大小进行从小到大的排序.

（3）对于排完序的 ans 数组，下标为 0 对应的线和下标为 1 对应的线在 minx 到 minx+1 之间所构成的封闭的空间是属于区域内部的；下标为 1 与下标为 2 所构成的空间属于外部；2-3 是内部，以此类推。

（4）针对于 ans[0] 我们需要求出线在 x=minx 处的纵坐标(并向上取整) y11，x = minx+1 处的纵坐标为（向上取整）y12：y1 = max(y11,y12);。对于 ans[1]，我们在求 x = minx 和 x = minx+1 处的纵坐标时向下取整得到 y21,y22：y2 = min(y21,y22);

if(y2-y1>0){sum += y2-y1;
}

x= x+1;循环第三步。

#include<iostream>
#include<math.h>
#include<algorithm>using namespace std;struct Point {//点int x;int y;
}P[1010];
struct Line{//线：两个点构成Point a;Point b;
}L[1010];
struct I_Y{//线的下标编号，还有对应的纵坐标int index;double y;
}ans[1010];
int N,sum = 0;//点的总数，方块的总数
bool cmp (struct I_Y a,struct I_Y b)//纵坐标排序
{return a.y<b.y;
}
int max(int a,int b)
{return a>b?a:b;
}
int min(int a,int b){return a>b?b:a;
}
double F_y(struct Line l,double x)//求线l经过横坐标为x的点的纵坐标，简单的几何计算。
{double x1 = fabs(l.a.x-l.b.x);double x2 = fabs(x - l.a.x);double y = (l.b.y-l.a.y)*x2/x1 + l.a.y;return y;
}
void solve()
{int minx ,maxx,i,j,k,count,ax,bx;minx = P[0].x;maxx = P[0].x;for(i=0;i<N;i++){//寻找最小、大横坐标if(P[i].x>maxx){maxx = P[i].x;}if(P[i].x<minx){minx = P[i].x;}}for(i=minx+1;i<=maxx;i++){//计算每个小长条中的小正方形数量count = 0;for(j=0;j<N;j++){ax = L[j].a.x;bx = L[j].b.x;if((ax<=i-1&&bx>=i) || (ax>=i && bx <=i-1)){//当这条线和x = i有交点时，记录线编号和交点纵坐标ans[count].index = j;ans[count].y = F_y(L[j],(i+i-1)/2.0);count++;}}sort(ans,ans+count,cmp);//排序for(k=0;k<count/2;k++){//向上取整函数 double ceil(double x) 向下取整是double floor(double x) 在#include<math.h>中int y1 = max((int)ceil(F_y(L[ans[k*2].index],i)),(int)ceil(F_y(L[ans[k*2].index],i-1)));int y2 = min((int)floor(F_y(L[ans[k*2+1].index],i)),(int)floor(F_y(L[ans[k*2+1].index],i-1)));//    printf("y1 = %d ,y2 = %d\n",y1,y2);if(y2-y1>0){sum+=y2-y1;}}}cout<<sum<<endl;
}
int main()
{int x,y;cin>>N;for(int i=0;i<N;i++){cin>>x>>y;P[i].x = x;P[i].y = y;}L[0].a = P[0];//第一个点和最后一个点构成一条线L[0].b = P[N-1];for(int i=1;i<N;i++){L[i].a = P[i];//相邻两点构成一条线L[i].b = P[i-1];}solve();return 0;
}

百分解法

本题需要先将所有的点按横坐标离散成一个个竖条的区间，最多不超过O(N)条，每条区间中最多不超过O(N)个小的梯形，总共不超过O(N^2)个梯形，然后再分别计算每个梯形中包含的整方块数量。

由于每个梯形的左右边（最左和最右的横坐标）都是整数，而纵坐标都是有理数，可以表示成P/Q的形式，对于这种梯形中整块的数量可以使用辗转相除法来加速计算，在O(log (PQ))的时间内求解。这一用法较难，也是本题的重要考查点。

本题的实现需要比较细致，梯形的情况需要考虑清楚才不会漏情况。

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;const int maxn=10000+10;
struct Tline
{bool flag;int x1,y1,x2,y2;long long a,b,c;
} L[maxn];
struct Tnode
{int x,y;
} P[maxn];
pair<double,int> rank[maxn];
int key[maxn];
int n;long long gcd(long long a,long long b)
{return !b?a:gcd(b,a%b);
}//计算sum(ceil((a*i+b)/c),0<=i<n)
long long calc(long long a,long long b,long long c,long long n)
{if (a<0) return calc(-a,b+a*(n-1),c,n);if (!n) return 0;long long res=0;if (a>=c) res+=n*(n-1)/2*(a/c);a%=c;if ((b<0?-b:b)>=c) res+=n*(b/c);b%=c;if (!a) return res;res+=calc(c,(a*n+b)%c,a,(a*n+b)/c);return res;
}long long floor(Tline &L,int xl,int xr)
{long long res=calc(L.a,L.b,L.c,xr+1);res-=calc(L.a,L.b,L.c,xl);return res;
}long long ceil(Tline &L,int xl,int xr)
{long long res=calc(L.a,L.b+L.c-1,L.c,xr+1);res-=calc(L.a,L.b+L.c-1,L.c,xl);return res;
}bool cmp(Tline &T0,Tline &T1,int x1,int x2)
{long long I1=((long long)T0.a*x1+T0.b)/T0.c;long long I2=((long long)T1.a*x2+T1.b)/T1.c;if (I1<=I2) return 1;if (I1-I2>1) return 0;int u=((long long)T0.a*x1+T0.b)%T0.c;int v=((long long)T1.a*x2+T1.b)%T1.c;return ((long long)u*T1.c-(long long)v*T0.c<0);
}long long work(Tline &L0,Tline &L1,int xl,int xr)
{    //除去左边floor<=ceil的情况if (cmp(L0,L1,xl+L0.flag,xl+!L1.flag)){int ll=xl-1,rr=xr+1;for (int mid;ll+1<rr;){mid=(ll+rr)/2;if (cmp(L0,L1,mid+L0.flag,mid+!L1.flag)) ll=mid;else rr=mid;}xl=rr;if (xl>xr) return 0;}//除去右边floor<=ceil的情况if (cmp(L0,L1,xr-!L0.flag,xr-L1.flag)){int ll=xl-1,rr=xr+1;for (int mid;ll+1<rr;){mid=(ll+rr)/2;if (cmp(L0,L1,mid-!L0.flag,mid-L1.flag)) rr=mid;else ll=mid;}xr=ll;if (xl>xr) return 0;}long long res=0;//计算上边界下方格点数if (L0.y1<L0.y2) res+=floor(L0,xl,xr-1);        //斜率>0else res+=floor(L0,xl+1,xr);    //斜率<0//计算下边界下方格点数if (L1.y1<L1.y2) res-=ceil(L1,xl+1,xr);else res-=ceil(L1,xl,xr-1);return res;
}void getline(Tline &T)
{long long a=T.y2-T.y1,b=T.x2-T.x1;long long c=gcd(a,b);a/=c;b/=c;if (b<0) b*=-1,a*=-1;T.a=a;T.c=b;T.b=b*T.y1-a*T.x1;T.flag=T.y1>T.y2;
}int main()
{
//    freopen("C.in","r",stdin);
//    freopen("C.out","w",stdout);scanf("%d",&n);for (int i=0;i<n;i++) {scanf("%d%d",&P[i].x,&P[i].y);key[i]=P[i].x;}for (int i=0;i<n;i++) {L[i].x1=P[i].x;L[i].y1=P[i].y;L[i].x2=P[(i+1)%n].x;L[i].y2=P[(i+1)%n].y;if (L[i].x1>L[i].x2) {swap(L[i].x1,L[i].x2);swap(L[i].y1,L[i].y2);}getline(L[i]);}long long res=0;sort(key,key+n);for (int i=0;i+1<n;i++)if (key[i]!=key[i+1]){int tot=0;for (int j=0;j<n;j++)if (L[j].x1<=key[i] && L[j].x2>=key[i+1])rank[tot++]=make_pair((double)(L[j].a*(double)(key[i]+key[i+1])/2.0+L[j].b)/L[j].c,j);sort(rank,rank+tot);if (tot&1) printf("-___-\n");int prev=res;for (int j=0;j<tot;j+=2){long long xx=res;res+=work(L[rank[j+1].second],L[rank[j].second],key[i],key[i+1]);//    if (key[i]==9)//    cout << res-xx << endl;}//    cout << key[i] << " " << key[i+1] << " " << res-prev << endl;}cout << res << endl;
}