Cod sursa(job #1574185)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 20 ianuarie 2016 11:52:56
Problema Gradina Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.27 kb
#include <fstream>
#include <algorithm>
#include <climits>
#include <vector>
#include <iomanip>
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);
       
    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 << fixed << setprecision(1) << (double) difMin / 2 << '\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.begin() + nr, 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;
    }
    
    uz[0] = false;
    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);
}