hdu - 4631 - Sad Love Story

題意：一個空平面，每次增加一個點，其坐標根據上一個點算出：(x[i-1] * Ax + Bx )  mod Cx，(y[i-1] * Ay + By )  mod Cy求出現有點集中的最近點對的距離的平方，共增加n個點，求每次求得的平方的和( n <= 5*100000, T(T <= 10)組測試數據)。

 ——>>時間給得挺長的，20s，不過暴力求還是會TLE……這裡進行貪心剪枝。

在已有點的集合中點按x坐標排序，每增一個點，就從這個點開始往右掃，掃到單單橫坐標的差的平方 >= Min就跳出，因為加上縱坐標的差的平方肯定 >= Min，且越往右越大；同理，從這個點的左邊第一個點開始往左掃，掃完後統計結果。

#include <cstdio>
#include <set>

using namespace std;

const int maxn = 500000 + 10;
const long long INF = (1LL<<60);
int n, x[maxn], y[maxn];

struct Point{
    int x;
    int y;
    bool operator < (const Point& e) const{
        return x < e.x;
    }
};

void read(int *a){
    int A, B, C, i;
    a[0] = 0;
    scanf("%d%d%d", &A, &B, &C);
    for(i = 1; i <= n; i++){
        a[i] = ((long long)a[i-1] * A + B) % C;
    }
}

long long solve(){
    int i;
    long long Min = INF, ret = 0;
    multiset<Point> se;
    se.clear();
    Point v;
    v.x = x[1];
    v.y = y[1];
    se.insert(v);
    for(i = 2; i <= n; i++){
        v.x = x[i];
        v.y = y[i];
        multiset<Point>::iterator p = se.lower_bound(v), iter;
        for(iter = p; iter != se.end(); iter++){        //從p開始，一直到se.end()前一個位置
            long long dx = v.x - iter->x;
            dx *= dx;
            if(dx >= Min) break;        //剪枝
            long long dy = v.y - iter->y;
            dy *= dy;
            Min = min(Min, dx + dy);
        }
        for(iter = p; iter != se.begin();){     //從p的上一個位置開始，一直算完se.begin()
            iter--;
            long long dx = v.x - iter->x;
            dx *= dx;
            if(dx >= Min) break;        //剪枝
            long long dy = v.y - iter->y;
            dy *= dy;
            Min = min(Min, dx + dy);
        }
        ret += Min;
        se.insert(v);
    }
    return ret;
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        read(x);
        read(y);
        printf("%I64d\n", solve());
    }
    return 0;
}