AllSib2011-Planetarium-Kuzkokov-Solution-155K

Просмотр исходного кода
Задача: Планетарий
Время: 16:26:57 7-11-11
Язык: MinGW C++ (GCC 4.6.1)

#define _USE_MATH_DEFINES
#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>

#define EPS 1e-6
#define GRID 15
#define BRIGHTEST 100

using namespace std;

struct point {
    double x;
    double y;
    double z;
    point() : x(0), y(0), z(0) { }
    point& operator-=(const point& b) {
        x-=b.x; y-=b.y; z-=b.z;
        return *this;
    }
    point& operator+=(const point& b) {
        x+=b.x; y+=b.y; z+=b.z;
        return *this;
    }
    double operator!() const {
        return x*x+y*y+z*z;
    }
    point& operator*=(const double& b) {
        x*=b; y*=b; z*=b;
        return *this;
    }
    point operator^(const point& b) const {
        point res;
        res.x = y*b.z - z*b.y;
        res.y = z*b.x - x*b.z;
        res.z = x*b.y - y*b.x;
        return res;
    }
    double operator*(const point& b) const {
        return x*b.x+y*b.y+z*b.z;
    }
};

struct point2d {
    double x;
    double y;
    point2d() : x(0), y(0) { }
    double operator!() const {
        return x*x+y*y;
    }
    point2d& operator*=(double b) {
        x*=b; y*=b;
        return *this;
    }
    point2d& operator+=(const point2d& b) {
        x+=b.x; y+=b.y;
        return *this;
    }
    point2d& operator-=(const point2d& b) {
        x-=b.x; y-=b.y;
        return *this;
    }
    bool operator< (const point2d& b) const {
        return (int)(GRID*x)==(int)(GRID*b.x) ? (int)(GRID*y)<(int)(GRID*b.y) : (int)(GRID*x)<(int)(GRID*b.x);
    }
    bool operator== (const point2d& b) const {
        return (int)(GRID*x)==(int)(GRID*b.x) && (int)(GRID*y)==(int)(GRID*b.y);
    }
};

struct star : point {
    double l;
    void read() {
        scanf("%lf%lf%lf%lf",&x,&y,&z,&l);
    }
    void normalize(const star& home) {
        *this -= home;
        double coef=1/!*this;
        *this *= sqrt(coef);
        l *= coef;
    }
    bool operator< (const star& b) const {
        return l > b.l;
    }
};

vector<star> tenture;

struct asterism : vector<point2d> {
    int vis;
    void read() {
        char str[256];
        gets(str);
                char* t=str;
        while(1) {
            char* s=t;
            double x = strtol(t,&t,10)-50;
            if (t==s) break;
            push_back(point2d());
            point2d& pt = *rbegin();
            pt.x = x;
            pt.y = strtol(t,&t,10)-50;
        }
        normalize();
    }
    void normalize() {
        double scale=0;
        point2d farthest;
        for(iterator it=begin();it!=end();++it) {
            double r2 = !*it;
            if (scale < r2) {
                scale = r2;
                farthest = *it;
            }
        }
        scale = 1/scale;
        for(iterator it=begin();it!=end();++it) {
            point2d res;
            res.x = it->x*farthest.x + it->y*farthest.y;
            res.y = it->y*farthest.x - it->x*farthest.y;
            res *= scale;
            *it = res;
        }
        sort(begin(),end());
    }
    bool operator==(const asterism& b) {
        //TODO optimize
        if (size() != b.size()) return false;
        vector<bool> marked;
        marked.resize(size());
        for(int i=0;i<size();i++) {
            point2d tmp = (*this)[i];
            tmp.x -= .5/GRID; tmp.y -= .5/GRID;
            int s = lower_bound(b.begin(),b.end(),tmp)-b.begin();
            while (s<size() && marked[s]) s++;
            if (tmp == b[s]) { marked[s]=true; continue; }
            tmp.x += 1./GRID;
            s = lower_bound(b.begin(),b.end(),tmp)-b.begin();
            while (s<size() && marked[s]) s++;
            if (tmp == b[s]) { marked[s]=true; continue; }
            tmp.x -= 1./GRID; tmp.y += 1./GRID;
            s = lower_bound(b.begin(),b.end(),tmp)-b.begin();
            while (s<size() && marked[s]) s++;
            if (tmp == b[s]) { marked[s]=true; continue; }
            tmp.x += 1./GRID;
            s = lower_bound(b.begin(),b.end(),tmp)-b.begin();
            while (s<size() && marked[s]) s++;
            if (tmp == b[s]) { marked[s]=true; continue; }
            return false;
        }
        return true;
    }
};

vector<asterism> asts;

void init() {
    freopen("input.txt","rt",stdin);
    freopen("output.txt","wt",stdout);
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++) {
        tenture.push_back(star());
        tenture.rbegin()->read();
    }
    int astn;
    int vis=1;
    while(scanf("%d\n",&astn) == 1) {
        for(int i=0;i<astn;i++) {
            asts.push_back(asterism());
            asterism& ast = *asts.rbegin();
            ast.read();
            ast.vis = vis;
        }
        vis++;
    }
}

struct celestialSphere : vector<star> {
    int homei;
    void normalize(const star& home) {
        for(int i=0;i<size();i++) {
            if (i==homei-1) {
                (*this)[i]=*rbegin();
                pop_back();
            }
            (*this)[i].normalize(home);
        }
        sort(begin(), end());
        }

    void findCloseStars(vector<star>& res,const star& anchor) {
        //TODO optimize
        double next=0;
        for(iterator it=begin(); it!=end(); ++it) {
            if (anchor*(*it) > cos(M_PI/18)) {
                if (it->l < next) break;
                next=0.2*it->l;
                res.push_back(*it);
                if (res.size() > 11) break;
            }
        }
    }

    void tryAsterism(const star& anchor) {
        vector<star> close;
        findCloseStars(close,anchor);
        if (close.size()<4 || close.size() > 10) return;
        point xx;
        for(vector<star>::iterator it=close.begin();it!=close.end();++it)
            xx += *it;
        xx *= 1/sqrt(!xx);
        point yy;
        yy.x = 1; yy.y = 0; yy.z = 0;
        yy = yy ^ xx;
        if (!yy < EPS) {
            yy.x = 0; yy.y = 1; yy.z = 0;
            yy = yy ^ xx;
        }
        point zz = xx^yy;
        asts.push_back(asterism());
        asterism& ast = *asts.rbegin();
        ast.vis = -homei;
        for(vector<star>::iterator it=close.begin();it!=close.end();++it) {
            ast.push_back(point2d());
            point2d& img = *ast.rbegin();
            img.x = zz*(*it);
            img.y = yy*(*it);
            img *= 1/(xx*(*it));
        }
        ast.normalize();
    }
};

void findAsterisms(int homei) {
    const star& home=tenture[homei];
    if (home.l>4) return;
    celestialSphere sphere;
    sphere.insert(sphere.begin(),tenture.begin(),tenture.end());
    sphere.homei = homei+1;
    sphere.normalize(home);
    for(int i=0;i<BRIGHTEST;i++) sphere.tryAsterism(sphere[i]);
}

int found[10100];
void examineSkies() {
    int vn = asts.rbegin()->vis;
    for(int i=0;i<tenture.size();i++) findAsterisms(i);
    //TODO optimize
    for(int i=0;i<asts.size();i++) {
        if (found[asts[i].vis]) continue;
        if (asts[i].vis<0) break;
        for(int j=asts.size()-1;j>=0;j--) {
            if (asts[j].vis>0) break;
            if (asts[i]==asts[j]) {
                found[asts[i].vis]=-asts[j].vis;
                break;
            }
        }
    }
    for(int i=1;i<=vn;i++) printf("%d\n",found[i]);
}

int main() {
    init();
    examineSkies();
    return 0;
}