Pagini recente » Cod sursa (job #2037138) | Cod sursa (job #255783) | Cod sursa (job #2426918) | Cod sursa (job #3178071) | Cod sursa (job #2576774)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <bitset>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int maxn = 120005;
pair <double, double> v[maxn];
bitset <maxn> pus;
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 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);
int poz = 0;
stk[++poz] = 1;
pus[1] = 1;
for(int i = 2; i <= n; i++)
{
pair <double, double> x = v[stk[poz - 1]];
pair <double, double> y = v[stk[poz]];
while(poz >= 2 && !det(x.first, x.second, y.first, y.second, v[i].first, v[i].second))
{
pus[stk[poz]] = 0;
poz--;
x = v[stk[poz - 1]];
y = v[stk[poz]];
}
stk[++poz] = i;
pus[i] = 1;
}
for(int i = n - 1; i >= 1; i--)
{
pair <double, double> x = v[stk[poz - 1]];
pair <double, double> y = v[stk[poz]];
if(!pus[i])
{
while(poz >= 2 && !det(x.first, x.second, y.first, y.second, v[i].first, v[i].second))
{
pus[stk[poz]] = 0;
poz--;
x = v[stk[poz - 1]];;
y = v[stk[poz]];
}
stk[++poz] = i;
pus[i] = 1;
}
}
pair <int, int> x = v[stk[poz - 1]];
pair <int, int> y = v[stk[poz]];
while(poz >= 2 && !det(x.first, x.second, y.first, y.second, v[1].first, v[1].second))
{
pus[stk[poz]] = 0;
poz--;
x = v[stk[poz - 1]];;
y = v[stk[poz]];
}
out << poz << "\n";
for(int i = 1; i <= poz; i++)
out << setprecision(6) << fixed << v[stk[i]].first << " " << setprecision(6) << fixed << v[stk[i]].second << "\n";
return 0;
}