Cod sursa(job #1573160)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 19 ianuarie 2016 14:28:25
Problema Gradina Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.23 kb
#include <fstream>
#include <algorithm>
#include <climits>
#include <vector>
#include <cmath>
using namespace std;
#define INF LLONG_MAX
#define Nmax 250
using ll = long long;
using pct = struct {int x, y, p;};
  
int n;
ll difMin;
int S[Nmax + 5];
pct v[Nmax], x[Nmax], y[Nmax];
vector< bool > sol(Nmax), aux(Nmax), uz(Nmax);
  
void read() ;
void write() ;
void check(int, int) ;
ll getArea(pct*, int) ;
ll cross_product(pct, pct, pct) ;
bool CMP(pct a, pct b)
{
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}
  
int main()
{
    int i, j;
      
    read();
    sort(v, v + n, CMP);
     
    check(5, 1);
      
    for(difMin = INF, i = 0; i < n; ++i)
        for(j = 0; j < n; ++j)
            if(i != j) check(i, j);
      
    write();
      
    return 0;
}
  
void read()
{
    int i;
    ifstream fin("gradina.in");
      
    fin >> n;
    for(i = 0; i < n; ++i)
    {
        fin >> v[i].x >> v[i].y;
        v[i].p = i;
    }
      
    fin.close();
}
  
void write()
{
    ofstream fout("gradina.out");
      
    fout << difMin / 2 << '.' << (difMin % 2 ? 5 : 0) << '\n';
      
    for(int i = 0; i < n; ++i)
        if(sol[i]) fout << 'V';
        else fout << 'I';
    fout << '\n';
      
    fout.close();
}
  
void check(int p1, int p2)
{
    int i, n1, n2;
    ll a1, a2, dif;
     
    for(n1 = n2 = 0, i = 0; i < n; ++i)
        if(i == p1)
        {
            if(p1 < p2) x[n1++] = v[i];
            else y[n2++] = v[i];
        }
        else if(i == p2)
        {
            if(p1 < p2) y[n2++] = v[i];
            else x[n1++] = v[i];
        }
        else if(cross_product(v[p1], v[p2], v[i]) > 0)
        {
            x[n1++] = v[i];
        }
        else
        {
            y[n2++] = v[i];
        }
     
    a1 = getArea(x, n1);
    a2 = getArea(y, n2);
    if(a1 == 0 || a2 == 0) return;
     
    for(i = 0; i < n1; ++i) aux[x[i].p] = true;
    for(i = 0; i < n2; ++i) aux[y[i].p] = false;
    if(sol[0] == true) for(i = 0; i < n; ++i) sol[i] = !sol[i];
     
    dif = a1 < a2 ? a2 - a1 : a1 - a2;
    if(dif < difMin)
    {
        difMin = dif;
        sol = aux;
    }
    else if(dif == difMin && sol > aux)
        sol = aux;
}
 
ll getArea(pct p[], int nr)
{
    if(nr < 3) return 0;
     
    int i, vf;
     
    fill(uz.begin(), uz.end(), 0);
    for(vf = 0, i = 0; i < nr; ++i)
        if(!uz[i])
    {
        while(vf >= 2 && cross_product(p[S[vf - 1]], p[S[vf]], p[i]) > 0)
            uz[S[vf]] = false, --vf;
         
        S[++vf] = i;
        uz[i] = true;
    }
     
    for(i = nr - 1; i >= 0; --i)
        if(!uz[i])
    {
        while(vf >= 2 && cross_product(p[S[vf - 1]], p[S[vf]], p[i]) > 0)
            uz[S[vf]] = false, --vf;
         
        S[++vf] = i;
        uz[i] = true;
    }
     
    if(vf < nr) return 0;
     
    ll area;
     
    S[0] = S[nr]; S[nr + 1] = S[1];
    for(area = 0, i = 1; i <= nr; ++i)
        area += 1LL * p[S[i]].x * (p[S[i + 1]].y - p[S[i - 1]].y);
         
    return area > 0 ? area : -area;
}
 
ll cross_product(pct a, pct b, pct c)
{
    return 1LL * (b.x - a.x) * (c.y - a.y)
            - 1LL * (b.y - a.y) * (c.x - a.x);
}