Pagini recente » Cod sursa (job #1822036) | Cod sursa (job #2195427) | Cod sursa (job #3170118) | Cod sursa (job #2122845) | Cod sursa (job #2110822)
#include <iostream>
#include <stdio.h>
#include <limits.h>
#include <algorithm>
using namespace std;
struct punct
{
double x, y;
}a[120001];
punct p;
bool comp(punct a, punct b)
{
return (a.y-p.y)/(a.x-p.x)<(b.y-p.y)/(b.x-p.x);
}
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;
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int n, poz=1, m=0;
punct v[120001];
p.x=p.y=INT_MAX;
cin>>n;
for(int i=1; i<=n; i++)
{
scanf("%lf %lf \n", &a[i].x, &a[i].y);
if((a[i].x<p.x) || (a[i].x==p.x && a[i].y<p.y))
{
p.x=a[i].x;
p.y=a[i].y;
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("%.6lf %.6lf \n", v[i].x, v[i].y);
return 0;
}