Pagini recente » Cod sursa (job #986126) | Cod sursa (job #2544999) | Cod sursa (job #2310996) | Cod sursa (job #1678827) | Cod sursa (job #1820222)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <bitset>
//#include <stack>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int maxn = 120005;
pair <double, double> v[maxn];
int pus[maxn];
int stk[maxn];
inline bool det(double x1, double y1, double x2, double y2, double x3, double y3)
{
if((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1) < 0)
return 0;
return 1;
}
int sz = 0;
inline void push(int x)
{
stk[++sz] = x;
pus[x] = 1;
}
inline void pop()
{
pus[stk[sz]] = 0;
sz--;
}
int main()
{
int n;
in >> n;
for(int i = 1; i <= n; i++)
in >> v[i].first >> v[i].second;
sort(v + 1, v + n + 1);
push(1);
for(int i = 2; i <= n; i++)
{
pair <double, double> x = v[stk[sz - 1]];
pair <double, double> y = v[stk[sz]];
while(sz >= 2 && !det(x.first, x.second, y.first, y.second, v[i].first, v[i].second))
{
pop();
x = v[stk[sz - 1]];;
y = v[stk[sz]];
}
push(i);
}
for(int i = n - 1; i >= 1; i--)
{
pair <double, double> x = v[stk[sz - 1]];
pair <double, double> y = v[stk[sz]];
if(!pus[i])
{
while(sz >= 2 && !det(x.first, x.second, y.first, y.second, v[i].first, v[i].second))
{
pop();
x = v[stk[sz - 1]];;
y = v[stk[sz]];
}
push(i);
}
}
pair <int, int> x = v[stk[sz - 1]];
pair <int, int> y = v[stk[sz]];
while(sz >= 2 && !det(x.first, x.second, y.first, y.second, v[1].first, v[1].second))
{
pop();
x = v[stk[sz - 1]];;
y = v[stk[sz]];
}
out << sz << "\n";
for(int i = 1; i <= sz; i++)
out << setprecision(6) << fixed << v[stk[i]].first << " " << setprecision(6) << fixed << v[stk[i]].second << "\n";
return 0;
}