Pagini recente » Cod sursa (job #2476685) | Cod sursa (job #770010) | Rating Boscanici Adrian Gabriel (gabiadi) | Cod sursa (job #945539) | Cod sursa (job #2691364)
#include <bits/stdc++.h>
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
const int NMAX = 120000;
pair<double, double> vec[1 + NMAX];
int vf;
int stiva[1 + NMAX];
const double EPS = 0.0000000000001;
inline double ccw(const pair<double, double>& o, const pair<double, double>& a, const pair<double, double>& b) /// B fata de vectorul OA(orientat de la O la A), e + pt stanga, - pt dreapta, 0 daca e pe OA
{
return (a.first - o.first) * (b.second - o.second) - (a.second - o.second) * (b.first - o.first);
}
bool comp(const pair<double, double>& a, const pair<double, double>& b)
{
return ccw(vec[1], a, b) > EPS;
}
int main()
{
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int n;
double minimX = 1000000001.0;
double minimY = 1000000001.0;
int index = -1;
in >> n;
for (int i = 1; i <= n; i++)
{
in >> vec[i].first >> vec[i].second;
if (vec[i].first < minimX)
{
minimX = vec[i].first;
minimY = vec[i].second;
index = i;
}
else if (vec[i].first == minimX)
{
if (vec[i].second < minimY)
{
minimY = vec[i].second;
index = i;
}
}
}
swap(vec[1], vec[index]);
vf++;
stiva[vf] = 1;
sort(vec + 1 + 1, vec + 1 + n, comp);
for (int i = 2; i <= n; i++)
{
while (vf >= 2 && ccw(vec[stiva[vf - 1]], vec[stiva[vf]], vec[i]) < EPS)
{
vf--;
}
vf++;
stiva[vf] = i;
}
out << vf << '\n' << fixed << setprecision(6);
for (int i = 1; i <= vf; i++)
{
out << vec[stiva[i]].first << ' ' << vec[stiva[i]].second << '\n';
}
return 0;
}