Pagini recente » Cod sursa (job #2644941) | Cod sursa (job #1112144) | Cod sursa (job #1898219) | Cod sursa (job #2826953) | Cod sursa (job #2110845)
#include <iostream>
#include <stdio.h>
#include <limits.h>
#include <algorithm>
using namespace std;
struct punct
{
double x, y;
}a[120001];
punct p;
int det(punct a, punct b, punct c)
{
int prod;
prod=(a.x*b.y)+(c.x*a.y)+(b.x*c.y)-(c.x*b.y)-(c.y*a.x)-(b.x*a.y);
return prod;
}
bool comp(punct A, punct B)
{
return det(a[1],A,B)>=0;
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int n, poz=1, m=0;
punct v[120001];
cin>>n;
for(int i=1; i<=n; i++)
{
scanf("%lf %lf \n", &a[i].x, &a[i].y);
if((a[i].y<a[poz].y) || (a[i].y==a[poz].y && a[i].x<a[poz].x))
poz=i;
}
swap(a[poz],a[1]);
sort(a+2,a+n+1,comp);
v[++m]=a[1];
v[++m]=a[2];
for(int i=3; i<=n; i++)
{
while(det(v[m-1],v[m],a[i])<=0)
{
m--;
}
v[++m]=a[i];
}
printf("%d \n", m);
for(int i=1; i<=m; i++)
printf("%.12lf %.12lf \n", v[i].x, v[i].y);
return 0;
}