Pagini recente » Cod sursa (job #1340039) | Cod sursa (job #1956151) | Cod sursa (job #757696) | Cod sursa (job #2855438) | Cod sursa (job #2193612)
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
#define INF 1000000001
int n;
struct punct
{
double x, y, unghi;
bool operator < (const punct& p) const
{
return unghi > p.unghi;
}
};
vector<punct> A;
vector<int> X;
double CalcCos(int a, int b)
{
double Cop, Cal, Ip;
Cop = A[b].y - A[a].y;
Cal = A[b].x - A[a].x;
Ip = sqrt(Cop * Cop + Cal * Cal);
if (Ip)return Cal/Ip;
else return 1;
}
double CalcUnghi(int a, int b, int c)
{
return (A[b].y - A[a].y)*(A[c].x - A[b].x) - (A[c].y - A[b].y) * (A[b].x - A[a].x);
}
int main()
{
fin >> n;
A = vector<punct>(n + 1);
int ind;
double xmin = INF, ymin = INF;
for (int i = 1; i <= n; i ++)
{
fin >> A[i].x >> A[i].y;
if ((A[i].y < ymin) || (A[i].y == ymin && A[i].x < xmin))
{
xmin = A[i].x;
ymin = A[i].y;
ind = i;
}
}
for (int i = 1; i <= n; i ++)
A[i].unghi = CalcCos(ind, i);
sort(A.begin() + 1, A.end());
X.push_back(1);
X.push_back(2);
X.push_back(3);
for (int i = 4; i <= n; i ++)
{
int sz = X.size();
while (sz >= 2 && CalcUnghi(X[sz - 2], X[sz - 1], i) > 0)
{
X.pop_back();
sz--;
}
X.push_back(i);
}
fout << X.size() << '\n';
for (unsigned int i = 0; i < X.size(); i ++)
fout << fixed << setprecision(7) << A[X[i]].x << ' ' << A[X[i]].y << '\n';
return 0;
}