Pagini recente » Cod sursa (job #239606) | Cod sursa (job #922027) | Cod sursa (job #1321813) | Cod sursa (job #2559209) | Cod sursa (job #2173662)
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstdio>
#define N 120005
#define inf 0x3f3f3f3f
using namespace std;
struct punct
{
double x, y, unghi;
}a[N], s[N];
int n, ns;
double xmin=inf, ymin=inf;
int cmp(punct e, punct f)
{
return (e.unghi<f.unghi);
}
int cmp2(punct e, punct f)
{
e.unghi=atan2(e.y, e.x);
f.unghi=atan2(f.y, f.x);
return (e.unghi<=f.unghi);
}
void citire()
{
scanf("%d\n", &n);
for(int i=1;i<=n;i++)
{
scanf("%lf %lf\n", &a[i].x, &a[i].y);
a[i].unghi=0;
if(a[i].x<xmin)
xmin=a[i].x, ymin=a[i].y;
else
if(a[i].x==xmin && a[i].y<ymin)
ymin=a[i].y;
}
}
void sortare_unghiuri()
{
for(int i=1;i<=n;i++)
if(xmin==a[i].x && ymin==a[i].y)
a[i].unghi=-10;
else
a[i].unghi=atan2(a[i].y-ymin, a[i].x-xmin);
sort(a+1, a+n+1, cmp);
}
double det(punct a, punct b, punct c)
{
return a.x*b.y+b.x*c.y+a.y*c.x-b.y*c.x-c.y*a.x-b.x*a.y;
}
void solutie()
{
s[++ns]=a[1];
s[++ns]=a[2];
for(int i=3;i<=n;i++)
{
punct p1=a[i], p2=s[ns], p3=s[ns-1];
while(det(p1, p2, p3)>0 && ns>1)
{
ns--;
p2=s[ns];
p3=s[ns-1];
}
s[++ns]=p1;
}
}
void afisare()
{
printf("%d\n", ns);
sort(s+1, s+ns+1, cmp2);
for(int i=1;i<=ns;i++)
printf("%lf %lf\n", s[i].x, s[i].y);
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
citire();
sortare_unghiuri();
// for(int i=1;i<=n;i++)
// printf("%lf %lf\n", a[i].x, a[i].y);
solutie();
afisare();
return 0;
}