Pagini recente » Cod sursa (job #685178) | Cod sursa (job #2031506) | Cod sursa (job #1176855) | Cod sursa (job #906551) | Cod sursa (job #3270247)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <climits>
#include <iomanip>
//#include <bits/stdc++.h>
#define in fin
#define out fout
using namespace std;
using db = double;
ifstream fin("gradina.in");
ofstream fout("gradina.out");
struct punct{
db x, y;
bool operator == (punct b){
return (b.x == x && b.y == y);
}
};
db det(punct a, punct b, punct c){
return ( a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - a.x * c.y - b.x * a.y );
}
punct start;
bool cmp(punct a, punct b){
if(a == start) return true;
if(b == start) return false;
return (det( start, a, b ) > 0);
}
bool e_convex(vector< punct > & v){
for(int i = 2; i < v.size(); i++){
if(det( v[i - 2], v[i - 1], v[i] ) < 0) return 0;
}
return 1;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n; in >> n;
punct v[n];
db mini = __DBL_MAX__;
start.x = start.y = 0;
for(int i = 0; i < n; i++) in >> v[i].x >> v[i].y;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i == j) continue;
vector< punct > st, dr;
for(int k = 0; k < n; k++){
if( det(v[i], v[j], v[k]) > 0 ) st.push_back(v[k]);
else dr.push_back(v[k]);
}
sort(st.begin(), st.end(), cmp);
sort(dr.begin(), dr.end(), cmp);
bool convex_1 = e_convex(st), convex_2 = e_convex(dr);
if(!convex_1 || !convex_2) continue;
// cout << "Stabilim I ( " << v[i].x << " , " << v[i].y << " ) si J ( " << v[j].x << " , " << v[j].y << " )\n";
// cout << " -- > st : ";
// for(int k = 0; k < st.size(); k++) cout << "( " << st[k].x << " , " << st[k].y << " ) ";
// cout << '\n';
// cout << " -- > dr : ";
// for(int k = 0; k < dr.size(); k++) cout << "( " << dr[k].x << " , " << dr[k].y << " ) ";
// cout << '\n';
db A1 = 0, A2 = 0;
for(int k = 0; k + 1 < st.size(); k++){
A1 += st[k].x * st[k + 1].y - st[k + 1].x * st[k].y;
}
A1 += st.back().x * st[0].y - st[0].x * st.back().y;
for(int k = 0; k + 1 < dr.size(); k++){
A2 += dr[k].x * dr[k + 1].y - dr[k + 1].x * dr[k].y;
}
A2 += dr.back().x * dr[0].y - dr[0].x * dr.back().y;
A1 /= 2; A2 /= 2;
// cout << " -- > A1 = " << A1 << " A2 = " << A2 << '\n';
mini = min(mini, abs(A1 - A2));
}
}
out << fixed << setprecision(6) << mini << '\n';
return 0;
}