杭州手机网站建设公司 网络服务,北海网站建设网络公司,莲花网站,建设公司网站价格bzoj4558 真是一道非常excited的题目啊…JLOI有毒 题目大意#xff1a;给一个(N1)*(M1)的网格图#xff0c;格点坐标为(0~N,0~M)#xff0c;现在挖去了K个点#xff0c;求剩下多少个正方形#xff08;需要注意的是正方形可以是斜着的#xff0c;多斜都可以#xff09; N…bzoj4558 真是一道非常excited的题目啊…JLOI有毒 题目大意给一个(N1)*(M1)的网格图格点坐标为(0~N,0~M)现在挖去了K个点求剩下多少个正方形需要注意的是正方形可以是斜着的多斜都可以 N,M10^6K2*10^3。 首先我们发现有一个非常感人的K0部分分… 我们考虑K0怎么做。 对于一个形如这样的正方形我们叫它(a,b)正方形好了。 我们可以很容易地发现一个(a,b)正方形实际上要占下(ab)*(ab)这么大一块网格。 然后我们考虑ab的大小这样a就是[0,ab]这么大这样就可以得到一个答案。 代码如下 现在我们发现有了这些障碍物我们只要能求出总共的正方形个数、经过一个障碍点的正方形个数、经过两个障碍点的正方形个数、经过三个点的、经过四个点的即可。 经过三个和经过四个直接二分查找一下显然是trivial的经过两个点的要考虑是作为边往两侧延伸和作为对角线的情况也比较trivial。 总共的正方形个数我们已经求出来了现在我们就要考虑经过某一个障碍点的正方形个数。 对于一个点和它相关的只有四个属性u,d,l,r对吧。 首先我们考虑直的正方形即(0,x)或(x,0)正方形因为这类正方形容易被重复统计。 容易发现这类正方形个数为min(u,l)min(u,r)min(l,d)min(d,r)。 其它的正方形显然都是在四个象限中某两个相邻象限的。 为了简化起见我们先考虑l,r,d这一象限的。 还是一样设正方形为(a,b)正方形我们枚举ab假设abc。 因为正方形不是直的所以a,b≠0。 现在我们考虑求出a的取值范围。 容易发现arac-1a1ac-l由于bl。 那么我们可以列出一个形如这样的式子来计算 这样显然不够优秀我们可以人工分类讨论一下… 额其实注意到当rc-1时cr1当c-l1时cl1那么min和max的两个“分界点”是l1和r1在分界点中间显然都是一些一次函数那么就都是等差数列于是我们就可以避免人工分类讨论了。 有了这个函数calc(l,r,d)那么calc(u,d,l,r)显然就等于 一些奇怪的细节详见代码… #include iostream
#include stdio.h
#include stdlib.h
#include algorithm
#include math.h
using namespace std;
typedef long long ll;
#define MOD 100000007
ll calc(ll l,ll r,ll d)
{if(!l||!r||!d) return 0;ll ans0;ll uppmin(lr,d);ll ps[3]{l1,r1,upp};sort(ps,ps3);ll cl1;for(int i0;i3;i){ll crps[i];if(crupp) break;if(cr2||clcr) continue;cl;ll vlmin(r,cl-1)-max(cl-l,1LL)1;ll vrmin(r,cr-1)-max(cr-l,1LL)1;ans(vlvr)*(cr-cl1)/2;ans%MOD;clcr;}return ans;
}
ll calc(ll u,ll d,ll l,ll r)
{return calc(u,d,l)calc(u,d,r)calc(l,r,u)calc(l,r,d)min(u,r)min(u,l)min(d,l)min(d,r);
}
typedef pairll,ll pll;
pll ps[233333];
#define X first
#define Y second
ll n,m,k,ans0;
bool ok(pll a)
{return a.X0a.Xna.Y0a.Ym;
}
ll tointt(double x)
{if(fabs(x-ll(x0.5))1e-5) return x0.5;return -1;
}
double chk(double x,double y)
{ll xxtointt(x),yytointt(y);if(xx0xxnyy0yym) return 1;return 0;
}
int main()
{cinnmk; n; m;ll cnt30,cnt40;for(ll g1;gngm;g) ans(n-g)%MOD*(m-g)%MOD*g%MOD, ans%MOD;for(int i1;ik;i){ll x,y;scanf(%lld%lld,x,y);ans-calc(x,n-1-x,y,m-1-y);ans%MOD;ps[i]pll(x,y);}sort(ps1,ps1k);for(int i1;ik;i){for(int ji1;jk;j){do{double mx(ps[i].Xps[j].X)/2.0,my(ps[i].Yps[j].Y)/2.0;double dxps[i].X-mx,dyps[i].Y-my;if(chk(mx-dy,mydx)chk(mxdy,my-dx)) ans;}while(0);for(int p-1;p1;p2){ll dxps[j].X-ps[i].X,dyps[j].Y-ps[i].Y;pll n1pll(ps[j].X-dy*p,ps[j].Ydx*p);pll n2pll(ps[i].X-dy*p,ps[i].Ydx*p);if(ok(n1)ok(n2));else continue;ans;int cp0;if(binary_search(ps1,ps1k,n1)) cp;if(binary_search(ps1,ps1k,n2)) cp;if(cp1) cnt3;else if(cp2) cnt3, cnt4;}}}ans-cnt3/2; ans-cnt4/4;printf(%d\n,int(((ans%MOD)MOD)%MOD));
} 转载于:https://www.cnblogs.com/zzqsblog/p/5493655.html
