Pagini recente » Cod sursa (job #2425927) | Cod sursa (job #2677571) | Cod sursa (job #2401291) | Cod sursa (job #1175628) | Cod sursa (job #1341270)
#include <iostream>
#include <stdio.h>
#include <algorithm>
#define Nmax 120005
#define x first
#define y second
using namespace std;
pair <double, double> pct[Nmax], S[Nmax];
int N, vf;
double det(pair<double, double> A, pair<double, double> B, pair<double, double> C)
{
return ((B.x - A.x)*(C.y - A.y) - (C.x - A.x)*(B.y - A.y));
}
class cmp{
public:
bool operator() (const pair<double, double> &A, const pair<double, double> &B) const
{
return (det(pct[1], A, B) < 0);
}
};
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &N);
for(int i=1;i<=N;++i)
scanf("%lf%lf", &pct[i].x, &pct[i].y);
int ind = 1;
for(int i=2;i<=N;++i)
if(pct[i] < pct[ind])
ind = i;
swap(pct[1], pct[ind]);
sort(pct+2, pct+N+1, cmp());
vf++;
S[vf] = pct[1];
vf++;
S[vf] = pct[2];
for(int i=3;i<=N;++i)
{
while(vf>=2 && det(S[vf-1], S[vf], pct[1]) > 0)
--vf;
vf++;
S[vf] = pct[i];
}
printf("%d\n", vf);
while(vf)
{
printf("%lf %lf\n", S[vf].x, S[vf].y);
vf--;
}
return 0;
}