Abstract

ZJU 3648 Gao the Grid II

组合计数 不等式

 

Body

第一次把一场浙大月赛的题目全部做完呢～对于小女这样的菜鸟来说，算是不小的成就，好开心呀～

Source

Description

求N x M的矩形网格中有多少个以格点为顶点的锐角三角形。

Solution

据说本题数据很水，可以O(N^4)乱搞过去。不过这里还是说说正经做法。

首先注意到任意一个三角形可以唯一确定一个包含它的最小矩形，并且三角形至少有一个顶点在矩形的顶点上。

然后可以发现，对于任意的锐角三角形，三个顶点一定都在矩形的边上。

如果我们知道给定大小的矩形上有多少个锐角三角形，我们就可以枚举矩形大小，算出大矩形内有多少个小矩形，乘上小矩形上的锐角三角形个数，最后再求和就可以了。

现在问题就是求给定大小的矩形上有多少个锐角三角形。设矩形大小为(i, j)，不妨令三角形的一个顶点在(i, j)上，如图。

现在要求alpha和beta都是锐角，用向量点积或者余弦定理都可以解出q*j>p*(i-p)以及p*i>q*(j-q)，且0<p<=i以及0<q<j。枚举p的话，q的解集是可以O(1)算出来的（一个一次不等式解集和一个二次不等式解集的交）。顶点在其它三个点的情况类似。

这样对于给定的(i, j)，锐角三角形的个数就可以O(N)求出。所以对于所有的(i, j)，只需要O(N^3)时间预处理统计。

具体实现时候，我用了当p递增时关于q的二次不等式解集的两个边界一增一减的性质，这样可以避免浮点运算和一大堆乱七八糟的讨论。

Code

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long long ll;int N, M;ll cnt[111][111];ll solve(int i, int j) {    ll res = 0;    int p, q, l = 0, r = j;    for (p = 1; p <= i; ++p) {        while (l
         
          l*(j-l)) ++l;        while (r>0 && l<=r && p*i>r*(j-r)) --r;        q = p*(i-p)/j;        if (q >= r) res += max(0, j-q-1);        else if (q >= l) res += max(0, j-r-1);        else res += max(0, j-r-1)+max(0, l-q-1);    }    return res;}int main() {    int i, j, p, q, l, r;    for (i = 1; i <= 100; ++i)        for (j = 1; j <= 100; ++j)            cnt[i][j] = solve(i, j)+solve(j, i)<<1;    while (cin>>N>>M) {        ll ans = 0;        for (i = 1; i <= N; ++i)            for (j = 1; j <= M; ++j)                ans += cnt[i][j]*(N-i+1)*(M-j+1);        cout<
          
           <<'\n'; } return 0;}