Pagini recente » Profil soso | Cod sursa (job #1537843) | Cod sursa (job #2273791) | Statistici Neghina Laurentiu (Laureniu) | Cod sursa (job #1796048)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <bitset>
#include <vector>
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(pair <double, double> x, pair <double, double> y, pair <double, double> z)
{
double x1 = x.first;
double y1 = x.second;
double x2 = y.first;
double y2 = y.second;
double x3 = z.first;
double y3 = z.second;
return ((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)) >= 0;
}
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 sz = 1;
stk[1] = 1;
pus[1] = 1;
for(int i = 2; i <= n; i++)
{
while(sz >= 2 && !det(v[stk[sz - 1]], v[stk[sz]], v[i]))
{
pus[stk[sz]] = 0;
sz--;
}
pus[i] = 1;
stk[++sz] = i;
}
for(int i = n - 1; i >= 1; i--)
{
if(pus[i] == 1)
continue;
while(sz >= 2 && !det(v[stk[sz - 1]], v[stk[sz]], v[i]))
{
pus[stk[sz]] = 0;
sz--;
}
pus[i] = 1;
stk[++sz] = i;
}
for(int i = 1; i <= n; i++)
if(pus[i] == 1)
out << setprecision(6) << fixed << v[stk[i]].first << " " << setprecision(6) << fixed << v[stk[i]].second << "\n";
return 0;
}