Pagini recente » Cod sursa (job #2216630) | Cod sursa (job #2458123) | Cod sursa (job #1141930) | Cod sursa (job #2965612) | Cod sursa (job #2611098)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("gradina.in");
ofstream g("gradina.out");
typedef pair < int, int > PII;
typedef pair < PII, int > PIII;
using ld = long double;
typedef pair < string, ld > Answer;
const int NMAX = 255;
const long long INF = 1LL * 1e18;
const ld eps = 1e-10, HALF = 0.5000000000, ONE = 1.0000000000;
int N;
PIII A[NMAX];
char S[NMAX];
static inline void Read ()
{
f.tie(nullptr);
f >> N;
for(int i = 1; i <= N; ++i)
f >> A[i].first.first >> A[i].first.second, A[i].second = i;
return;
}
static inline ld Frac (ld a, ld b)
{
return (ld)(a / b) * ONE;
}
int Stiva[NMAX], K;
bool Sel[NMAX];
static inline long long Det2 (PII A, PII B)
{
return (1LL * A.first * B.second - 1LL * A.second * B.first);
}
static inline long long Det3 (PII A, PII B, PII C)
{
return (1LL * A.first * B.second + 1LL * B.first * C.second + 1LL * C.first * A.second) - (1LL * B.second * C.first + 1LL * C.second * A.first + 1LL * A.second * B.first);
}
static inline ld my_abs (ld X)
{
if(X < eps)
return -X;
return X;
}
static inline pair < bool, ld > ConvexHull (vector < int > Set, char Fill)
{
for(auto it : Set)
S[A[it].second] = Fill;
for(int i = 1; i <= N; ++i)
Sel[i] = 0;
K = 0;
///
Stiva[++K] = Set[0];
Stiva[++K] = Set[1];
Sel[Set[1]] = 1;
for(int i = 2; i < (int)Set.size(); ++i)
{
while(K > 1 && Det3(A[Set[i]].first, A[Stiva[K - 1]].first, A[Stiva[K]].first) > 0)
{
Sel[Stiva[K]] = 0;
--K;
}
Stiva[++K] = Set[i];
Sel[Set[i]] = 1;
}
for(int i = (int)Set.size() - 1; i >= 0; --i)
if(!Sel[Set[i]])
{
while(K > 1 && Det3(A[Set[i]].first, A[Stiva[K - 1]].first, A[Stiva[K]].first) > 0)
{
Sel[Stiva[K]] = 0;
--K;
}
Stiva[++K] = Set[i];
Sel[Set[i]] = 1;
}
if(Stiva[K] != Stiva[1])
Stiva[++K] = Stiva[1];
///
int r = 0;
for(int i = 1; i <= N; ++i)
r += Sel[i];
if(r != (int)Set.size())
return {0, 0};
ld Area = 0;
for(int i = 1; i < K; ++i)
Area += Det2(A[Stiva[i]].first, A[Stiva[i + 1]].first);
Area = my_abs(Area);
Area *= HALF;
return {1, Area};
}
static inline Answer GetSol (int Ind1, int Ind2)
{
Answer r;
r.second = INF;
vector < int > Set_1, Set_2;
for(int i = 1; i <= N; ++i)
{
if(i == Ind1)
{
Set_1.push_back(i);
continue;
}
if(i == Ind2)
{
Set_2.push_back(i);
continue;
}
if(A[Ind1].first.first == A[Ind2].first.first)
{
if(A[i].first.first <= A[Ind1].first.first)
Set_1.push_back(i);
else
Set_2.push_back(i);
continue;
}
if(A[Ind1].first.second == A[Ind2].first.second)
{
if(A[i].first.second <= A[Ind1].first.second)
Set_1.push_back(i);
else
Set_2.push_back(i);
continue;
}
ld m = Frac(A[Ind1].first.second - A[Ind2].first.second, A[Ind1].first.first - A[Ind2].first.first);
ld b = (ld)(A[Ind1].first.second) - m * (ld)(A[Ind1].first.first);
ld Height_Line = (ld)(A[i].first.first) * m + b;
if((ld)A[i].first.second - Height_Line < eps)
Set_1.push_back(i);
else
Set_2.push_back(i);
}
if((int)Set_1.size() < 3 || (int)Set_2.size() < 3)
return r;
pair < bool, ld > P_1 = ConvexHull(Set_1, 'I');
pair < bool, ld > P_2 = ConvexHull(Set_2, 'V');
if(!P_1.first || !P_2.first)
return r;
r.second = my_abs(P_1.second - P_2.second);
if(S[1] == 'V')
{
for(int i = 1; i <= N; ++i)
if(S[i] == 'V')
S[i] = 'I';
else
S[i] = 'V';
}
for(int i = 1; i <= N; ++i)
r.first.push_back(S[i]);
return r;
}
static inline void Afis (ld X)
{
X *= (ld)10.0000000000;
long long Y = X;
g << (Y / 10LL) << '.' << (Y % 10LL) << '\n';
return;
}
static inline void Solve ()
{
sort(A + 1, A + N + 1);
Answer ans;
ans.second = INF;
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= N; ++j)
if(i != j)
{
Answer Now = GetSol(i, j);
if(Now.second < ans.second)
ans = Now;
else if(Now.second == ans.second && Now.first < ans.first)
ans = Now;
}
Afis(ans.second);
g << ans.first << '\n';
return;
}
int main()
{
Read();
Solve();
return 0;
}