Pagini recente » Cod sursa (job #2323615) | Cod sursa (job #2249016) | Cod sursa (job #2323269) | Cod sursa (job #3227835) | Cod sursa (job #3198161)
// 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;
int orientation (point a, point b, point c){
return (b.y - a.y) * (c.x - b.x) - (c.y - b.y) * (b.x - a.x);
}
bool cmp (point a, 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 (half.size() >= 2 && orientation(half[k-2], half[k-1], half[k]) > 0)
return false; // am gasit un punct care se afla in interior
return true;
}
double heron (double a, double b, double c){
double p = (a + b + c) / 2;
double arie = p*(p-a)*(p-b)*(p-c);
arie = sqrt(arie);
return arie;
}
double distance (point a, point b){
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double arie (){
double rez = 0.0;
for (int i=1; i<half.size() - 1; ++i){
double ab = distance (half[0], half[i]);
double bc = distance (half[i], half[i+1]);
double ac = distance (half[0], half[i+1]);
rez += heron (ab, bc, ac);
}
return rez;
}
bool cmpByName (char name, int 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){
int 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 == -1 || arie2 == -1)
return;
potential = arie2 - arie1;
if (potential < 0)
potential = -potential;
if (potential < rez){
rez = potential;
strcpy(finalAns, ans);
}
else if (fabs(potential - rez) < 0.001 && strcmp(finalAns, ans) > 0){
strcpy(finalAns, ans);
rez = potential;
}
}
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;
}