Cod sursa(job #3198183)

Utilizator Teodor94Teodor Plop Teodor94 Data 28 ianuarie 2024 14:43:53
Problema Gradina Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.81 kb
// sursa ioana badu
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cstring>
#define N_MAX 255

using namespace std;

ifstream in("gradina.in");
ofstream out("gradina.out");

struct point {int x, y;};

point points[N_MAX];
vector <point> half;
char ans[N_MAX], finalAns[N_MAX];
int n;
double rez = 10e9;

long long orientation (const point& a, const point& b, const point& c){
    return ((long long)b.y - a.y) * (c.x - b.x) - ((long long)c.y - b.y) * (b.x - a.x);
}

bool cmp (const point& a, const point& b){
    return orientation (half.front(), a, b) < 0;
}

int findFirst (){
    int rez = 0;

    for (int k=1; k<half.size(); ++k){
        if (half[k].x < half[rez].x || (half[k].x == half[rez].x && half[k].y < half[rez].y))
            rez = k;
    }

    return rez;
}

bool infasuratoare (){
    if (half.size() <= 2)
        return false;

    for (int k=2; k<half.size(); ++k)
        if (orientation(half[k-2], half[k-1], half[k]) > 0)
            return false; // am gasit un punct care se afla in interior
    return true;
}

double arietriunghi (const point& p1, const point& p2, const point& p3) {
    return (double)((long long)p1.x * (p2.y - p3.y) + (long long)p2.x * (p3.y - p1.y) + (long long)p3.x * (p1.y - p2.y)) / 2;
}

double arie (){
    double rez = 0.0;

    for (int i=1; i<half.size() - 1; ++i){
        rez += arietriunghi(half[0], half[i], half[i + 1]);
    }

    return rez;
}

bool cmpByName (char name, long long var){
    if (name == 'I'){
        if (var < 0)
            return true;
        return false;
    }
    else{
        if (var > 0)
            return true;
        return false;
    }
    return false;
}

double compute (int i, int j, char name){
    for (int k=0; k<n; ++k){
        if (k != i && k != j){
            long long o = orientation (points[i], points[j], points[k]);
            if (cmpByName(name, o)){
                half.push_back(points[k]);
                ans[k] = name;
            }
        }
    }
    swap (half[0], half[findFirst()]);
    sort (half.begin(), half.end(), cmp);

    if (infasuratoare() == false){
        return -1;
    }

    double halfAria = arie();

    return halfAria;
}

void computeFinalAnswer (double arie1, double arie2){
    double potential;

    if (arie1 < -0.5 || arie2 < -0.5)
        return;

    potential = arie2 - arie1;
    if (potential < 0)
        potential = -potential;

    if (fabs(potential - rez) < 0.001 && strcmp(finalAns, ans) > 0){
        strcpy(finalAns, ans);
        rez = potential;
    } else if (potential < rez){
        rez = potential;
        strcpy(finalAns, ans);
    }
}

int main (){
    in >> n;

    for (int i=0; i<n; ++i){
        in >> points[i].x >> points[i].y;
    }

    double arieIon, arieVasile;
    for (int i=0; i<n; ++i){
        for (int j=i+1; j<n; ++j){
            if (i != j){ // am nevoie de fix doua puncte (a caror dreapta sa-mi desparta planul in doua)
                ans[i] = 'I', ans[j] = 'I';
                half.push_back(points[i]);
                half.push_back(points[j]);
                arieIon = compute(i, j, 'I');
                arieVasile = compute(i, j, 'V');

                computeFinalAnswer(arieIon, arieVasile);
                half.clear();

                ans[i] = 'V', ans[j] = 'V';
                half.push_back(points[i]);
                half.push_back(points[j]);
                arieVasile = compute(i, j, 'V');
                arieIon = compute(i, j, 'I');

                computeFinalAnswer(arieIon, arieVasile);
                half.clear();
            }
        }
    }

    out << setprecision(1) << fixed << rez << '\n';
    out << finalAns;
    return 0;
}