Cod sursa(job #429533)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 30 martie 2010 11:25:44
Problema Gradina Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.03 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <deque>
#include <vector>
using namespace std;

const int maxn = 300;
const int INF = 1100000000;

int X[maxn],Y[maxn];
//int  V[maxn];
int PI,IND[maxn],N,ST[maxn], punct_initial, M, nr1, nr2, set1x[maxn], set1y[maxn], set2x[maxn], set2y[maxn];
long long Sol;
vector < pair <int, int> > v;
vector < pair <int, int> > Sol1, Sol2;

pair < pair <int, int>, pair <int, int> > A[maxn];

inline bool cmpf(int i,int j)
{
	return 1LL * (X[i] - X[PI]) * (Y[j] - Y[PI]) < 1LL * (X[j] - X[PI]) * (Y[i] - Y[PI]);
}

inline long long llabs (long long x) {
    return x > 0 ? x : -x;
}

inline long long semn(int i1,int i2,int i3)
{
	return (long long)1LL * X[i1] * Y[i2] + 1LL * X[i2] * Y[i3] + 1LL * X[i3] * Y[i1] - 1LL * Y[i1] * X[i2] - 1LL * Y[i2] * X[i3] - 1LL * Y[i3] * X[i1];
}

inline long long det (int a, int b, int c, int d, int x, int y) {
   // printf("%d ", abs(a * d + c * y + b * x - x * d - b * c - y * a));
    return (1LL * a * d + 1LL * c * y + 1LL * b * x - 1LL * x * d - 1LL * b * c - 1LL * y * a);
}

vector < pair <int, int > > convex_hull (int X[], int Y[], int N) {
    int i;

    punct_initial = 0;
    ST[0] = 0; IND[0] = 0;

    for (i = 1; i <= N; ++ i) {
		if (X[i] < X[punct_initial] || (X[i] == X[punct_initial] && Y[i] < Y[punct_initial])) punct_initial = i;
    }

	PI = punct_initial;

	for(int i = 1;i <= N; ++i)
	{
		if (i == punct_initial) continue; 
		IND[++IND[0]] = i;
	}
	sort(IND + 1,IND + IND[0] + 1,cmpf);
	ST[ST[0] = 1] = punct_initial;
	for(int i = 1;i <= IND[0]; ++i) {
		while(ST[0] >= 2 && semn(ST[ST[0] - 1],ST[ST[0]],IND[i]) > 0) --ST[0];
		ST[++ST[0]] = IND[i];
	}
	ST[++ST[0]] = punct_initial;
	reverse(ST + 1, ST + ST[0] + 1);

    vector < pair <int, int> > ret;

    for (i = 1; i < ST[0]; ++ i)
        ret.push_back(make_pair(X[ST[i]], Y[ST[i]]));

    return ret;
}

long long area (int X[], int Y[], int nr1) {
    vector < pair <int, int> > p = convex_hull(X, Y, nr1);
    
    int x = p.size();
    long long ret = 0;

    for (int i = 0; i < x; ++ i)
        ret += (1LL * p[i].first * p[(i + 1) % x].second) - (1LL * p[i].second * p[(i + 1) % x].first);
    return llabs(ret);
}

void solve () {
    int i;
    long long a, b;
/*
    printf("**********************************\n");
    for (i = 1; i <= nr1; ++ i)
        printf("(%d %d) ", set1x[i], set1y[i]);
    puts("");
    for (i = 1; i <= nr2; ++ i)
        printf("(%d %d) ", set2x[i], set2y[i]);
    puts("");
*/
    if (nr1 < 3 || nr2 < 3)     return ;

    //fprintf(stderr, "OK");

    a = area (set1x, set1y, nr1);
    b = area (set2x, set2y, nr2);

    if (abs(a - b) < Sol) {
        Sol = abs(a - b);
        Sol1.clear(); Sol2.clear();
        for (i = 1; i <= nr1; ++ i)
            Sol1.push_back(make_pair(set1x[i], set1y[i]));
        for (i = 1; i <= nr2; ++ i)
            Sol2.push_back(make_pair(set2x[i], set2y[i]));
    }
}

int main() {
    int i, j, k;

	freopen("gradina.in","r",stdin);
	freopen("gradina.out","w",stdout);
	scanf("%d\n",&N);

	X[0] = INF;Y[0] = INF; Sol = 10000000000000000LL;
	for(i = 1;i <= N; ++i) {
		scanf("%d %d",&X[i],&Y[i]);
		if (X[i] < X[punct_initial] || (X[i] == X[punct_initial] && Y[i] < Y[punct_initial])) punct_initial = i;
	}

    vector < pair < int, int > > puncte = convex_hull(X, Y, N);

    for (i = 0; i < (int) puncte.size(); ++ i)
        for (j = 0; j < (int) puncte.size(); ++ j)
            if (i != j) {
                nr1 = 0; nr2 = 0;
     //           printf("I = (%d %d) J = (%d %d)\n", puncte[i].first, puncte[i].second, puncte[j].first, puncte[j].second);
      //          fprintf(stderr, "*");

                for (k = 1; k <= N; ++ k)
                    if (det(puncte[i].first, puncte[i].second, puncte[j].first, puncte[j].second, X[k], Y[k]) < 0) {
                        ++ nr1;
                        set1x[nr1] = X[k];
                        set1y[nr1] = Y[k];
                    } else if (det(puncte[i].first, puncte[i].second, puncte[j].first, puncte[j].second, X[k], Y[k]) > 0) {
                        ++ nr2;
                        set2x[nr2] = X[k];
                        set2y[nr2] = Y[k];
                    }

                // primul caz

                ++ nr1; set1x[nr1] = puncte[i].first; set1y[nr1] = puncte[i].second;
                ++ nr1; set1x[nr1] = puncte[j].first; set1y[nr1] = puncte[j].second;
                solve();

                // al doilea caz

                nr1 -= 2;
                ++ nr1; set1x[nr1] = puncte[i].first; set1y[nr1] = puncte[i].second;
                ++ nr2; set2x[nr2] = puncte[j].first; set2y[nr2] = puncte[j].second;
                solve();

                //puts("");
            }

    printf("%.1lf\n", 1.00 * Sol / 2);

//    for (i = 0; i < (int) Sol1.size(); ++ i)
  //      printf("(%d %d) ", Sol1[i].first, Sol1[i].second);
   // puts("");

    for (i = 1; i <= N; ++ i) {
        bool ok = 0;
        pair <int, int> x = make_pair(X[i], Y[i]);
        for (j = 0; j < (int) Sol1.size(); ++ j)
            if (x == Sol1[j])
                ok = 1;
        printf("%c", ok == 1 ? 'I' : 'V');
    }
	return 0;
}