Cod sursa(job #430739)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 31 martie 2010 12:18:11
Problema Gradina Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.25 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  V[maxn];
int PI,IND[maxn],N,ST[maxn], punct_initial, M, nr1, nr2, set1x[maxn], set1y[maxn], set2x[maxn], set2y[maxn], X[maxn], Y[maxn], XX[maxn], YY[maxn];
long long Sol;
vector < pair <int, int> > Sol1, Sol2;

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

inline long long semn(const int &i1, const int &i2, const 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 (const int &a, const int &b, const int &c, const int &d, const int &x, const 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 F1[], int F2[], int N) {
    int i;

    punct_initial = 0;
    ST[0] = 0; IND[0] = 0;
    X[0] = INF; Y[0] = INF;

    for (i = 1; i <= N; ++ i) {
        X[i] = F1[i];
        Y[i] = F2[i];
    }

    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];
	}

    vector < pair <int, int> > ret;

    for (i = 1; i <= ST[0]; ++ i)
        ret.push_back(make_pair(X[ST[i]], Y[ST[i]]));
    //for (i = 1; i < ST[0]; ++ i)
      //  printf("[%d %d] ", X[ST[i]], Y[ST[i]]);
    //puts("");
    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);
        //printf("[%d %d] ", p[i].first, p[i].second, ret);
    }
    //puts("");
    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);

  //  printf("A = %lld B = %lld\n\n", a, b);

    if (llabs(a - b) < Sol) {
        Sol = llabs(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);

	Sol = 1LL << 62;

	for (i = 1;i <= N; ++i) {
		scanf("%d%d", &XX[i], &YY[i]);
	}

    vector < pair < int, int > > puncte = convex_hull(XX, YY, N);

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

    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, XX[k], YY[k]) < 0) {
                        ++ nr1;
                        set1x[nr1] = XX[k];
                        set1y[nr1] = YY[k];
                    } else if (det(puncte[i].first, puncte[i].second, puncte[j].first, puncte[j].second, XX[k], YY[k]) > 0) {
                        ++ nr2;
                        set2x[nr2] = XX[k];
                        set2y[nr2] = YY[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(XX[i], YY[i]);
        for (j = 0; j < (int) Sol1.size(); ++ j)
            if (x == Sol1[j])
                ok = 1;
        printf("%c", ok == 1 ? 'I' : 'V');
    }
	return 0;
}