Pagini recente » Cod sursa (job #753449) | Cod sursa (job #24180) | Cod sursa (job #794411) | Cod sursa (job #1394473) | Cod sursa (job #917737)
Cod sursa(job #917737)
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAX 120001
int N , k , X[MAX];
struct punct{double x , y;bool d;}P[MAX],st[MAX];
bool comp(punct a , punct b)
{
if(a.y == b.y)return a.x<b.x;
return a.y<b.y;
}
void citire();
void solve();
void tipar();
void adauga(int i);
bool det(punct a , punct b , punct c)
{
if(a.x*b.y+b.x*c.y+c.x*a.y-b.y*c.x-c.y*a.x-b.x*a.y > 0)
return 1;
return 0;
}
int main()
{
citire();
solve();
tipar();
return 0;
}
void citire()
{
freopen("infasuratoare.in" , "r" , stdin );
scanf("%d" , &N );
for(int i = 1 ; i <= N ; ++i )
scanf("%lf%lf" , &P[i].x , &P[i].y) ;
}
void solve()
{
sort(P+1,P+N+1,comp);
st[1] = P[1];st[2] = P[2];X[1] = 1;X[2] = 2;k = 2;
P[1].d = P[2].d = 1;
for(int i = 3 ; i <= N ; ++i )
adauga(i);
for(int i = N ; i ; i--)
if(!P[i].d)adauga(i);
if(!det(st[k-1],st[k],st[1]))k--;
}
void adauga(int i)
{
if(det(st[k-1],st[k],P[i] ))
{
st[++k] = P[i];
X[k] = i;
P[i].d=1;
}
else
{
P[X[k]].d = 0;
int j = k-1;
while(!det(st[j-1],st[j],P[i]) && j > 1)
{
P[X[j]].d=0;
j--;
}
st[j+1] = P[i];
k = j+1;
X[k] = i;
P[i].d = 1;
}
}
void tipar()
{
freopen("infasuratoare.out" , "w" , stdout );
printf("%d\n" , k);
for(int i = 1 ; i <= k ; ++i )
printf("%lf %lf\n" , st[i].x , st[i].y);
}