2015 TopCoder Open - Round 1

SmallPolygons.cpp

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>

using namespace std;

class SmallPolygons
{
public:
    vector<string> choosePolygons(vector<int> points, int N);
};

int n;
vector<int> px;
vector<int> py;

bool cross(int p1, int p2, int q1, int q2)
{
    if (p1==q1 || p1==q2 || p2==q1 || p2==q2)
    {
        if (p1==q2)
            swap(q1, q2);
        else if (p2==q1)
            swap(p1, p2);
        else if (p2==q2)
            swap(p1, p2),
            swap(q1, q2);

        int x1 = px[p2] - px[p1];
        int y1 = py[p2] - py[p1];
        int x2 = px[q2] - px[q1];
        int y2 = py[q2] - py[q1];

        return x1*y2 == x2*y1 && x1*x2>=0 && y1*y2>=0;
    }

    if (max(px[p1], px[p2]) < min(px[q1], px[q2]) ||
        max(px[q1], px[q2]) < min(px[p1], px[p2]) ||
        max(py[p1], py[p2]) < min(py[q1], py[q2]) ||
        max(py[q1], py[q2]) < min(py[p1], py[p2]))
        return false;

    return (long long)((px[p2]-px[p1])*(py[q1]-py[p1])-(py[p2]-py[p1])*(px[q1]-px[p1])) *
           ((px[p2]-px[p1])*(py[q2]-py[p1])-(py[p2]-py[p1])*(px[q2]-px[p1])) <=0 &&
           (long long)((px[q2]-px[q1])*(py[p1]-py[q1])-(py[q2]-py[q1])*(px[p1]-px[q1])) *
           ((px[q2]-px[q1])*(py[p2]-py[q1])-(py[q2]-py[q1])*(px[p2]-px[q1])) <= 0;
}

bool cross(int l1, int l2, int p)
{
    return (px[l1]-px[p])*(py[l2]-py[p]) == (px[l2]-px[p])*(py[l1]-py[p]) &&
           min(px[l1], px[l2])<=px[p] && px[p]<=max(px[l1], px[l2]) &&
           min(py[l1], py[l2])<=py[p] && py[p]<=max(py[l1], py[l2]);
}

int area(int p1, int p2, int p3)
{
    return abs((px[p2]-px[p1])*(py[p3]-py[p1])-(py[p2]-py[p1])*(px[p3]-px[p1]));
}

bool inner(int p, vector<int> &v)
{
    int c = 0;

    for (int i=0; i<(int)v.size(); i++)
    {
        int p1 = v[i];
        int p2 = v[(i+1)%(int)v.size()];

        if (py[p1]==py[p] && px[p1]>=px[p] && py[p2]>py[p] ||
            py[p2]==py[p] && px[p2]>=px[p] && py[p1]>py[p] ||
            (py[p1]-py[p])*(py[p2]-py[p])<0 &&
            abs((py[p2]-py[p])*px[p1]-(py[p1]-py[p])*px[p2]) >= px[p]*abs((py[p2]-py[p])-(py[p1]-py[p])))
            c++;
    }

    return c%2!=0;
}

vector<string> SmallPolygons::choosePolygons(vector<int> points, int N)
{
    n = (int)points.size()/2;
    px.resize(n);
    py.resize(n);
    for (int i=0; i<n; i++)
        px[i] = points[2*i],
        py[i] = points[2*i+1];

    N = min(N, n/3);

    vector<vector<int> > P(N);

    int score = 3000000*N;

    for (int i=0; i<n; i++)
    {
        int ma = 999999999;
        int mp= -1;
        int midx = -1;

        for (int p=0; p<N; p++)
        {
            int pl = (int)P[p].size();

            if (pl == 0)
            {
                int a = -1000000;
                if (a < ma)
                    ma = a,
                    mp = p,
                    midx = -1;
                continue;
            }

            for (int idx=0; idx<pl; idx++)
            {
                bool f = true;
                for (int tp=0; tp<N && f; tp++)
                {
                    int tl = (int)P[tp].size();
                    if (tl>=2)
                    for (int tidx=0; tidx<tl; tidx++)
                        if (cross(P[p][idx],        i, P[tp][tidx], P[tp][(tidx+1)%tl]) ||
                            cross(P[p][(idx+1)%pl], i, P[tp][tidx], P[tp][(tidx+1)%tl]))
                            f = false;
                }

                if (f)
                {
                    int a = area(P[p][idx], P[p][(idx+1)%pl], i);
                    if (inner(i, P[p]))
                        a = -a;

                    if (pl<3)
                        a -= 1000000;

                    if (a < ma)
                        ma = a,
                        mp = p,
                        midx = idx;
                }
            }
        }

        if (mp == -1)
        {
            cerr<<"error "<<i<<endl;
            continue;
        }

        P[mp].insert(P[mp].begin()+(midx+1), i);
        score += ma;
    }

    cerr<<score*.5<<endl;

    vector<string> ret;
    for (auto &p: P)
    {
        string s;
        for (int a: p)
        {
            if (s != "")
                s += " ";
            stringstream ss;
            ss<<a;
            s += ss.str();
        }
        ret.push_back(s);
    }

    return ret;
}

#if TOPCODER_LOCAL

int main()
{
    int Np;
    cin>>Np;
    vector<int> points(Np);
    for (int &p: points)
        cin>>p;
    int N;
    cin>>N;

    SmallPolygons sp;
    vector<string> ret = sp.choosePolygons(points, N);
    
    cout<<ret.size()<<endl;
    for (string &r: ret)
        cout<<r<<endl;
    return 0;
}

#endif