hdu 4631 Sad Love Story(最近點對+暴力)

這題第一次做的時候覺得太暴力了。。不敢搞。。今天看了題解，一共有三種方法可以搞：sol 1是用STL暴力的。。簡單粗暴，但是考慮到自己的時間復雜度分析以及對數據的理解不夠深，比賽的時候還是慎用STL的好。sol 2是用KD樹，那是什麼。。。無奈只能嘗試一下sol 3了。。先求出所有點的最近點對，然後，對於這對點之後出現的點，累加就行了，然後不斷減少上界，直到大於1為止（一個點的時候無距離）。要改一下Closest_Pair的模板，使其返回最近點對的下標然後才能減少上界。。。10+Y，給hdu的long long輸入輸出跪了，最後怒換cin cout。。。。

 
#include<algorithm>  
#include<iostream>  
#include<cstring>  
#include<cstdlib>  
#include<fstream>  
#include<sstream>  
#include<bitset>  
#include<vector>  
#include<string>  
#include<cstdio>  
#include<cmath>  
#include<stack>  
#include<queue>  
#include<stack>  
#include<map>  
#include<set>  
#define FF(i, a, b) for(int i=a; i<b; i++)  
#define FD(i, a, b) for(int i=a; i>=b; i--)  
#define REP(i, n) for(int i=0; i<n; i++)  
#define CLR(a, b) memset(a, b, sizeof(a))  
#define debug puts("**debug**")  
#define LL long long  
#define PB push_back  
#define eps 1e-10  
using namespace std;  
const LL INF = 1LL << 50;  
const int N = 500005;  
  
template <class T> T sqr(T x) { return x*x; }  
struct Point  
{  
    LL x, y;  
    //id1用於求Closest_Pair id2用於求每次找到的上界  
    int id1, id2;  
    Point(){}  
    Point(LL x, LL y, int id2):x(x), y(y), id2(id2) {}  
}p[N], point[N], tmpt[N];  
int n;  
  
bool cmpxy(const Point& a, const Point& b)  
{  
    return a.x < b.x || (a.x == b.x && a.y < b.y);  
}  
bool cmpy(const Point& a, const Point& b)  
{  
    return a.y < b.y;  
}  
LL dist(Point a, Point b) //dist函數注意不要sqrt  
{  
    return sqr(a.x-b.x) + sqr(a.y-b.y);  
}  
  
struct Ans  
{  
    int l, r;  
    Ans(){}  
    Ans(int l, int r):l(l), r(r){}  
};  
  
Ans Closest_Pair(int left, int right)  
{  
    LL d = INF;  
    //由於函數返回結構體 原先模板中只有1或2個點時統一考慮  
    if(left==right || left+1 == right) return Ans(left, right);  
  
    int mid = (left+right)>>1;  
  
    Ans ans1 = Closest_Pair(left, mid);  
    double d1;  
    if(ans1.l == ans1.r) d1 = INF; //只有一個點的時候無距離  
    else d1 = dist(point[ans1.l],point[ans1.r]);  
  
    Ans ans2 = Closest_Pair(mid+1, right);  
    double d2;  
    if(ans2.l == ans2.r) d2 = INF;  
    else d2 = dist(point[ans2.l], point[ans2.r]);  
  
    Ans ret;  
    if(d1 < d2) ret = ans1;  
    else ret = ans2;  
  
    d = min(d1,d2);  
    int i,j,k=0;  
    for(i = left; i <= right; i++)  
    {  
        if(sqr(point[mid].x-point[i].x) <= d) //這裡也需要改 因為dist函數變了  
            tmpt[k++] = point[i];  
    }  
    sort(tmpt,tmpt+k,cmpy);  
    for(i = 0; i < k; i++)  
    {  
        for(j = i+1; j < k && sqr(tmpt[i].y-tmpt[j].y) < d; j++)//這裡也是。。。  
        {  
            double d3 = dist(tmpt[i],tmpt[j]);  
            if(d > d3)  
            {  
                d = d3;  
                ret = Ans(tmpt[i].id1, tmpt[j].id1);  
            }  
        }  
    }  
    return ret;  
}  
  
void read()  
{  
    LL a1, b1, c1, a2, b2, c2;  
    cin>>a1>>b1>>c1>>a2>>b2>>c2;  
    p[0] = Point(0, 0, 0);  
    FF(i, 1, n+1) p[i] = Point((p[i-1].x*a1+b1)%c1, (p[i-1].y*a2+b2)%c2, i);  
}  
  
int main()  
{  
    int T; scanf("%d", &T);  
    while(T--)  
    {  
        scanf("%d", &n);  
        read();  
        int end = n;  
        LL ans = 0;  
        while(end > 1)  
        {  
            REP(i, end) point[i] = p[i+1];  
            sort(point, point+end, cmpxy);  
            REP(i, end) point[i].id1 = i;  
  
            Ans t = Closest_Pair(0, end-1);  
            int m = max(point[t.l].id2, point[t.r].id2);  
            ans += (end-m+1)*dist(point[t.l], point[t.r]);  
            end = m - 1;  
        }  
        cout<<ans<<endl;  
    }  
    return 0;  
}