Pagini recente » Cod sursa (job #342470) | Cod sursa (job #3129480) | Cod sursa (job #543576) | Cod sursa (job #1780633) | Cod sursa (job #2691780)
#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>& a, const pair<double, double>& b)
{
return a.first * b.second - a.second * b.first;
}
bool comp(const pair<double, double>& a, const pair<double, double>& b)
{
//return ccw(a, b) > EPS;
return atan2(a.second, a.first) < atan2(b.second, b.first);
}
inline double ccw(const pair<double, double>& o, const pair<double, double>& a, const pair<double, double>& b)
{
return (a.first - o.first) * (b.second - o.second) - (a.second - o.second) * (b.first - o.first);
}
int main()
{
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int n;
double gX = 0.0;
double gY = 0.0;
in >> n;
for (int i = 1; i <= n; i++)
{
in >> vec[i].first >> vec[i].second;
gX += vec[i].first;
gY += vec[i].second;
}
gX /= (n * 1.0);
gY /= (n * 1.0);
//out << gX << ' ' << gY << '\n';
for (int i = 1; i <= n; i++)
{
vec[i].first -= gX;
vec[i].second -= gY;
}
sort(vec + 1, vec + 1 + n, comp);
/*
for (int i = 1; i <= n; i++)
{
out << vec[i].first + gX << ' ' << vec[i].second + gY << '\n';
}
*/
vf++;
stiva[vf] = 1;
vec[n + 1].first = vec[1].first;
vec[n + 1].second = vec[1].second;
for (int i = 2; i <= n + 1; i++)
{
while (vf >= 2 && ccw(vec[stiva[vf - 1]], vec[stiva[vf]], vec[i]) < EPS)
{
vf--;
}
vf++;
stiva[vf] = i;
}
vf--;
out << vf << '\n' << fixed << setprecision(6);
for (int i = 1; i <= vf; i++)
{
out << vec[stiva[i]].first + gX << ' ' << vec[stiva[i]].second + gY << '\n';
}
return 0;
}