TopCoder Marathon Match 61 "Planarity"

README.md

http://community.topcoder.com/longcontest/?module=ViewStandings&rd=14337

submit.cpp

#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <cstdlib>
#include <ctime>
#include <cmath>

using namespace std;

typedef unsigned int uint;

static const int V_MAX = 100;
static const int SQ_MAX = 700;
// static const int SEARCH_RADIUS = 20;
static const int RADIUS_MIN = 30;
// static const int RADIUS_MAX = 300;
// static const int TMP_PARAM = 100;
// static const int TMP = 1000000;
// static const double TMP_RATE = 0.95;
static const int MOVE_RANGE = 200;

#define TRIAL

static const double EPS = 1e-9;

// static const int TRIAL_MAX = 500;
static const int CHANGE_POINT = 20;
// static const int DIV_PARAM = 20;

struct P {
    int x, y;
    P() {}
    vector<pair<int, bool> > belongs_to;

    P(const int x_, const int y_) : x(x_), y(y_) {}

    inline bool operator ==(const P& p) const {
        return (p.x == x && p.y == y);
    }

    void move(int nextX, int nextY) {
        x = nextX;
        y = nextY;
    }
};

struct G2D {
    inline static P substr(const P& p1, const P& p2) {
        return P(p1.x - p2.x, p1.y - p2.y);
    }

    inline static double norm(const P& p) {
        return sqrt(p.x * p.x + p.y * p.y);
    }

    inline static int dot(const P& p1, const P& p2) {
        return p1.x*p2.x+p1.y*p2.y;
    }

    inline static int cross(const P& p1, const P& p2) {
        return p1.x*p2.y - p1.y*p2.x;
    }

    inline static double dist(const P& p1, const P& p2) {
        return norm(substr(p1, p2));
    }
};

struct Edge {
    P p1, p2, vect; // 始点、終点、相対ベクトル
    double norm; // 長さ
    Edge() {}
    Edge(const P& p1n, const P& p2n) : p1(p1n), p2(p2n) {
        calc_vect_and_norm();
    }

    Edge(const int p1x, const int p1y, const int p2x, const int p2y) : p1(P(p1x, p1y)), p2(P(p2x, p2y)) {
        calc_vect_and_norm();
    }

    void calc_vect_and_norm() {
        vect = G2D::substr(p2, p1);
        norm = G2D::norm(vect);
    }

    bool eq(const double a, const double b) const {
        return abs(a - b) < EPS;
    }

    /*
    bool intersect(const Edge& e) const {
        P a2a1 = G2D::substr(p2, p1);
        P b1a1 = G2D::substr(e.p1, p1);
        P b2a1 = G2D::substr(e.p2, p1);
        P b2b1 = G2D::substr(e.p2, e.p1);
        P a1b1 = G2D::substr(p1, e.p1);
        P a2b1 = G2D::substr(p2, e.p1);
        return (G2D::cross(a2a1, b1a1) * G2D::cross(a2a1, b2a1) < EPS) &&
               (G2D::cross(b2b1, a1b1) * G2D::cross(b2b1, a2b1) < EPS);
    }
    */

    bool intersect(const Edge& e) const {
        if  (min(p1.x, p2.x) > max(e.p1.x, e.p2.x)) return false;
        if  (max(p1.x, p2.x) < min(e.p1.x, e.p2.x)) return false;
        if  (min(p1.y, p2.y) > max(e.p1.y, e.p2.y)) return false;
        if  (max(p1.y, p2.y) < min(e.p1.y, e.p2.y)) return false;

        int den = G2D::cross(vect, e.vect);
        // int den = e.vect.y*vect.x-e.vect.x*vect.y;

        int num1 = e.vect.x*(p1.y-e.p1.y)-e.vect.y*(p1.x-e.p1.x);
        int num2 =   vect.x*(p1.y-e.p1.y)-  vect.y*(p1.x-e.p1.x);

        if (den == 0) {
            if(min(e.dist2(*this), dist2(e)) > 0) return false;

            if ((p1==e.p1 && eq(G2D::dist(p2, e.p2), norm + e.norm)) ||
                    (p1==e.p2 && eq(G2D::dist(p2, e.p1), norm + e.norm)) ||
                    (p2==e.p1 && eq(G2D::dist(p1, e.p2), norm + e.norm)) ||
                    (p2==e.p2 && eq(G2D::dist(p1, e.p1), norm + e.norm)))
                return false;
            return true;
        }

        if (p1 == e.p1 || p1 == e.p2 || p2 == e.p1 || p2 == e.p2)
            return false;

        double u1 = 1.0 * num1 / den;
        double u2 = 1.0 * num2 / den;
        if (u1 < 0 || u1 > 1 || u2 < 0 || u2 > 1)
            return false;

        return true;
    }

    double dist(const P& p) const {
        //distance from p to the edge
        if (G2D::dot(vect, G2D::substr(p, p1))<=0)
            return G2D::dist(p, p1);            //from p to p1
        if (G2D::dot(vect, G2D::substr(p, p2))>=0)
            return G2D::dist(p, p2);            //from p to p2
        //distance to the line itself
        return abs(-vect.y*p.x+vect.x*p.y+p1.x*p2.y-p1.y*p2.x)/norm;
    }

    double dist2(const Edge& other) const {
        //distance from the closest of the endpoints of "other" to "this"
        return min(dist(other.p1), dist(other.p2));
    }
};

uint get_random(const uint max) {
    return (unsigned int)(rand() / (RAND_MAX + 1.0) * max);
    // return rand() % max;
}

double get_random() {
    return (rand() / (RAND_MAX + 1.0));
}

struct Planarity {

    int calc( const vector<Edge>& edges ) {
        /* １点だけ移動させたときは、全部数え直す必要は無いような気がする */
        // N: number of edges # => E.size() / 2
        // １重ループ２回でできそうな気がする
        const int edges_size = edges.size();

        // int cnt = 0;
        // みんな最初に１ポイント持っている
        int cnt = 1;

        for(int i = 0; i < edges_size; ++i) {
            for(int j = 0; j < i; ++j) {
                if (edges[i].intersect(edges[j]))
                    cnt++;
            }
        }

        return cnt;
    }

    // edgesに対して破壊的変更が加えられます
    // 変更点の差分を返す
    int diff( vector<Edge>& edges, const P& p) {
        const int belongs_to_size = (int)p.belongs_to.size();
        const int edges_size = edges.size();
        int prev = 0;
        int next = 0;

        for(int i = 0; i < belongs_to_size; ++i) {
            pair<int, bool> e = p.belongs_to[i];

            for(int j = 0; j < edges_size; ++j) {
                if(j == e.first) continue;

                if(edges[e.first].intersect(edges[j]))
                    prev++;
            }

            // change
            if(e.second == true) {
                edges[e.first].p1 = p;
            }
            else {
                edges[e.first].p2 = p;
            }

            edges[e.first].calc_vect_and_norm();

            for(int j = 0; j < edges_size; ++j) {
                if(j == e.first) continue;
                if(edges[e.first].intersect(edges[j]))
                    next++;
            }
        }

        return next - prev;
    }

    inline bool in_sqrt(const int x1, const int y1, const int x2, const int y2, const int r) {
        const int dx = x2 - x1;
        const int dy = y2 - y1;
        return r * r > (dx * dx + dy * dy);
    }

    vector<int> untangle(const int V, const vector<int>& E) {
        clock_t start, end;
        start = clock();

        srand(static_cast<unsigned int>(time(NULL)));
        // srand(938);

        // V: number of vertices
        // E: E[2*j+1], E[2*j+1] is indices of vertices
        const int edges_size = E.size() / 2;

        static bool vis[SQ_MAX][SQ_MAX];
        memset(vis, 0, sizeof vis);

        vector<P> points(V);
        for(int i = 0; i < V; ++i) {
            int p, q;
            do {
                p = get_random(SQ_MAX);
                q = get_random(SQ_MAX);
            } while (vis[p][q]);

            vis[p][q] = true;
            points[i].x = p;
            points[i].y = q;
        }

        vector<Edge> edges(edges_size);
        for(int i = 0; i < edges_size; ++i) {
            int p = E[2*i];
            int q = E[2*i+1];
            edges[i] = Edge(points[p], points[q]);
            points[p].belongs_to.push_back(make_pair(i, true));
            points[q].belongs_to.push_back(make_pair(i, false));
        }

        vector<int> random_index(V);
        for(int i = 0; i < V; ++i)
            random_index[i] = i;
        random_shuffle(random_index.begin(), random_index.end());

        int cur_index = 0;

        int trial = 0;

        // double tmp = V * TMP_PARAM;

        while(true) {
            int r = random_index[cur_index++];
            if(cur_index == V) {
                cur_index = 0;
                random_shuffle(random_index.begin(), random_index.end());
            }

            int best_diff = 0;
            int best_x = points[r].x;
            int best_y = points[r].y;

            vis[best_x][best_y] = false;

            for(int change = 0; change < CHANGE_POINT; ++change) {
                int rx, ry;

                /*
                do {
                    rx = get_random(SQ_MAX);
                    ry = get_random(SQ_MAX);
                // } while(in_sqrt(rx, ry, best_x, best_y, SEARCH_RADIUS) || vis[rx][ry]);
                // } while(in_sqrt(rx, ry, best_x, best_y, 700 / (trial / 100 + 1)) || vis[rx][ry]);
                // } while(in_sqrt(rx, ry, best_x, best_y, max(SQ_MAX * DIV_PARAM / (trial + 1), RADIUS_MIN)) == false || vis[rx][ry]);
                } while(in_sqrt(rx, ry, best_x, best_y, max(SQ_MAX / (trial / 500 + 1), RADIUS_MIN)) == false || vis[rx][ry]);
                // } while(vis[rx][ry]);
                */

                do {
                    int range = MOVE_RANGE / (trial / 500 + 1);
                    rx = best_x + get_random(2 * range + 1) - range;
                    ry = best_y + get_random(2 * range + 1) - range;
                } while(!(0 <= rx && rx < SQ_MAX && 0 <= ry && ry < SQ_MAX) ||  vis[rx][ry]);


                points[r].x = rx;
                points[r].y = ry;

                // int cur_diff = diff(edges, points[r]) - best_diff;
                int cur_diff = diff(edges, points[r]);
                if(cur_diff < best_diff) {
                // if(cur_diff < 0 || exp(cur_diff / tmp)<= get_random()) {
                    best_diff = cur_diff;
                    // best_diff -= cur_diff;
                    best_x = rx;
                    best_y = ry;
                }
            }

            points[r].x = best_x;
            points[r].y = best_y;
            diff(edges, points[r]);

            vis[best_x][best_y] = true;

            trial++;

            end = clock();
            if(end - start > 9000000) break;
        }

        fprintf(stderr, "trial: %d\n", trial);

#if 0
        fprintf(stderr, "first: %d\n", first);
        fprintf(stderr, "from diff: %d\n", first + diff_point);
        fprintf(stderr, "second: %d\n", second);
        fflush(stderr);
#endif

#if 0
        int cnt = calc(edges);
        fprintf(stderr, "my count: %d\n", cnt);
        fflush(stderr);
#endif
        // res[2*j], res[2*j+1] が頂点jのx,y座標

        vector<int> res(2 * V);
        for(int i = 0; i < V; ++i) {
            res[2 * i] = points[i].x;
            res[2 * i + 1] = points[i].y;
        }

        return res;
    }
};

/*
int main() {
    //   10  <= V <=   100
    // 2 * V <= N <= 5 * V - 1
    int V, N;
    scanf("%d%d", &V, &N);

    vector<int> E(N);

    for(int i = 0; i < N; ++i) {
        scanf("%d", &E[i]);
    }

    // -----debug-----
#if 0

    fprintf(stderr, "%d %d\n", V, N);

    for(int i = 0; i < N; ++i) {
        fprintf(stderr, "%d\n", E[i]);
    }
#endif

    // -----debug-----


    Planarity p;
    vector<int> coords = p.untangle(V, E);
    for(int i = 0; i < (int)coords.size(); ++i) {
        printf("%d\n", coords[i]);
    }

    fflush(stdout);
}
*/