Pagini recente » Cod sursa (job #1992980) | Cod sursa (job #1225616) | Cod sursa (job #3253533) | Cod sursa (job #2479565) | Cod sursa (job #3198184)
// 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){
half.clear();
return -1;
}
double halfAria = arie();
half.clear();
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);
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);
}
}
}
out << setprecision(1) << fixed << rez << '\n';
out << finalAns;
return 0;
}