LA 6666 Directional Resemblance

三維的最近點對XDD

題目是這樣的: 給你一堆向量，問夾角最小的兩個向量?

把他們normalize，找最近點對

#include<cstdio>
#include<cstdlib>
#include<utility>
#include<cmath>
#include<map>
#include<set>
#include<algorithm>
#include<vector>
#define eps 0.00000001
using namespace std;
typedef long long int int64;
typedef pair<int64,int64> pii;
struct pack{
    int64 xx, yy, zz;
    double x, y, z;
    int ord;
}ps[130000];
int pcnt = 0;
bool cmp1(pack a, pack b){return a.xx<b.xx;}
bool cmp2(pack a, pack b){return a.x<b.x;}
double dist(int _a, int _b){
    pack& a = ps[_a], b = ps[_b];
    double dx = a.x-b.x, dy = a.y-b.y, dz = a.z-b.z;
    return sqrt(dx*dx + dy*dy + dz*dz);
}
double dist(pair<int,int> a){ return dist(a.first, a.second);}
pair<int,int> make(pair<int,int> a){
    pack& pa = ps[a.first],
          pb = ps[a.second];
    if(pair<int64,pii >(pa.xx, pii(pa.yy, pa.zz)) <
       pair<int64,pii >(pb.xx, pii(pb.yy, pb.zz))){
        return pair<int,int>(a.first, a.second);
    }
    return pair<int,int>(a.second, a.first);
}
pair<int,int> betterans(pair<int,int> a, pair<int,int> b){
    pair<int,int> aa = make(a);
    pair<int,int> bb = make(b);
    pack& a1 = ps[aa.first], a2 = ps[aa.second];
    pack& b1 = ps[bb.first], b2 = ps[bb.second];
    if(fabs(dist(aa)-dist(bb))<eps){
        //printf("0a0\n");
        if(pair<pair<int64,pii>, pair<int64,pii> >
            (pair<int64,pii>(a1.xx, pii(a1.yy, a1.zz)),
               pair<int64,pii>(a2.xx, pii(a2.yy, a2.zz))) > 
           pair<pair<int64,pii>, pair<int64,pii> >
            (pair<int64,pii>(b1.xx, pii(b1.yy, b1.zz)),
               pair<int64,pii>(b2.xx, pii(b2.yy, b2.zz))))
            return bb;
        else
            return aa;
        
    }
    return (dist(aa) >= dist(bb)+eps) ? bb:aa;
}
pair<int,int> ans(int l, int r){
    if(r - l <= 3){
        // assert l+1 <= r
        pair<int,int> ret = make(pair<int,int>(l,l+1));
        for(int lx = l;lx <= r;lx++)
            for(int ly = lx+1;ly <= r;ly++)
                ret = betterans(ret, pair<int,int>(lx,ly));
        return ret;
    }
    int mid = (l+r)/2;
    pair<int,int> getans = betterans(ans(l, mid), ans(mid+1, r));
    double getrr = dist(getans);
    map<pair<int64,int64>,vector<int> > leftmap, rightmap;
    for(int lx = l;lx <= mid ;lx++){
        int64 cx = (int64)(ceil(ps[lx].x/getrr));
        int64 cy = (int64)(ceil(ps[lx].y/getrr));
        //printf("%lld, %lld\n", cx, cy);
        leftmap[pii(cx, cy)].push_back(lx);
    }
    for(int lx = mid+1;lx <= r;lx++){
        int64 cx = (int64)ceil(ps[lx].x/getrr);
        int64 cy = (int64)ceil(ps[lx].y/getrr);
        rightmap[pii(cx, cy)].push_back(lx);
    }
    for(map<pii, vector<int> >::iterator it = leftmap.begin();
                it != leftmap.end(); it++){
        vector<int>& base = it->second;
        for(int64 dx = -2;dx <= 2;dx++){
        for(int64 dy = -2;dy <= 2;dy++){
            pii np(dx+it->first.first, dy+it->first.second);
            if(rightmap.count(np)){
                vector<int>& test = rightmap[np];
                for(int bb = 0;bb < base.size();bb++)
                    for(int tt = 0;tt < test.size();tt++)
                        getans = betterans(getans, pair<int,int>(base[bb], test[tt]));
            }
        }}
    }
    return getans;
}
int main()
{
    int m, n, S, W;
    for(;;){
        scanf("%d %d %d %d", &m, &n, &S, &W);
        if(m+n+S+W == 0) break;
        pcnt = 0;
        set<pair<int64,pii> > JJ;
        for(int lx = 0;lx < m;lx++){
            int64 xx, yy, zz;
            scanf("%lld %lld %lld", &xx, &yy, &zz);
            int64 ggg = __gcd(xx, __gcd(yy, zz));
            pair<int64,pii> G(xx/ggg,pii(yy/ggg,zz/ggg));
            if(JJ.count(G)) continue;
            JJ.insert(G);
            ps[pcnt].xx = xx, ps[pcnt].yy = yy, ps[pcnt].zz = zz;
            pcnt++;
            
        }
        int g = S;
        for(int lx = m;lx < n+m;lx++){
            int64 xx, yy, zz;
            xx = (g/7)%100 + 1;
            yy = (g/700)%100 + 1;
            zz = (g/70000)%100 + 1;
            if(g%2 == 0){g = g/2;}
            else {g = (g/2)^W;}
            int64 ggg = __gcd(xx, __gcd(yy, zz));
            pair<int64,pii> G(xx/ggg,pii(yy/ggg,zz/ggg));
            
            if(JJ.count(G)) continue;
            JJ.insert(G);
            ps[pcnt].xx = xx, ps[pcnt].yy = yy, ps[pcnt].zz = zz;
            pcnt++;
        }
        for(int lx = 0;lx < pcnt;lx++){
            double rr = sqrt(ps[lx].xx*ps[lx].xx + 
                        ps[lx].yy*ps[lx].yy + 
                        ps[lx].zz*ps[lx].zz); 
            ps[lx].x = ps[lx].xx/rr*100000;
            ps[lx].y = ps[lx].yy/rr*100000;
            ps[lx].z = ps[lx].zz/rr*100000;
        }
        sort(ps, ps+pcnt, cmp2);
        pair<int,int> getans = ans(0, pcnt-1);
        pack& pa = ps[getans.first], pb = ps[getans.second];
        printf("%lld %lld %lld %lld %lld %lld\n",pa.xx, pa.yy, pa.zz,
                                                pb.xx, pb.yy, pb.zz);
    }
    return 0;
}