Pagini recente » Cod sursa (job #853009) | Cod sursa (job #489123) | Cod sursa (job #449078) | Cod sursa (job #3130383) | Cod sursa (job #385852)
Cod sursa(job #385852)
#include <cstdio>
#include <algorithm>
#include <cmath>
#define N 121000
using namespace std;
struct nod
{
double x, y;
bool operator < (const nod &a) const
{
if(x < a.x) return 1;
if(x == a.x && y < a.y) return 1;
return 0;
}
};
nod a[N];
int n;
nod LS[N], LI[N];
int ns, ni;
void read()
{
freopen("infasuratoare.in","r",stdin);
scanf("%d\n", &n);
for(int i = 1; i <= n; ++i)
scanf("%lf %lf\n", &a[i].x, &a[i].y);
}
inline int isleft(nod p0, nod p1, nod p2)
{
double x = (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
if(fabs(x - 0) < 1e-10) return 0;
if(x < 0) return -1;
if(x > 0) return 1;
}
void solve()
{
sort(a+1,a+n+1);
LS[++ns] = a[1];
LS[++ns] = a[2];
int i;
for(i = 3; i <= n; ++i)
{
while(ns > 2 && isleft(a[i], LS[ns], LS[ns - 1]) < 0)
--ns;
LS[++ns] = a[i];
}
LI[++ni] = a[n];
LI[++ni] = a[n-1];
for(i = n - 2; i >= 1; --i)
{
while(ni > 2 && isleft(a[i], LI[ni], LI[ni - 1]) < 0)
--ni;
LI[++ni] = a[i];
}
freopen("infasuratoare.out","w",stdout);
printf("%d\n", ns + ni - 2);
for(i = ns - 1; i ; --i)
printf("%lf %lf\n", LI[i].x, LI[i].y);
for(i = ni - 1; i ; --i)
printf("%lf %lf\n", LS[i].x, LS[i].y);
}
int main()
{
read();
solve();
return 0;
}