Pagini recente » Cod sursa (job #2989540) | Cod sursa (job #229728) | Cod sursa (job #384906) | Cod sursa (job #2753350) | Cod sursa (job #434852)
Cod sursa(job #434852)
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAXN 120005
int N;
double X[MAXN], Y[MAXN];
int ind[MAXN];
int ST[MAXN];
int PCT = 1;
void citire()
{
scanf("%d",&N);
for(int i = 1 ; i <= N ; i++)
{
scanf("%lf%lf", &X[i], &Y[i]);
if(X[i] < X[PCT] || (X[i] == X[PCT] && Y[i] < Y[PCT]))
PCT = i;
ind[i] = i;
}
swap(X[1], X[PCT]);
swap(Y[1], Y[PCT]);
PCT = 1;
}
bool cmp(int i,int j)
{
return (X[i] - X[PCT]) * (Y[j] - Y[PCT]) > (X[j] - X[PCT]) * (Y[i] - Y[PCT]);
}
double prod(int i1,int i2,int i3)
{
//negativ daca se afla in dreapta dreptei suport
return (X[i2] - X[i1]) * (Y[i3] - Y[i1]) - (X[i3] - X[i1]) * (Y[i2] - Y[i1]);
}
void stiva()
{
ST[++ST[0]] = PCT;
ST[++ST[0]] = ind[2];
for(int i = 3 ; i <= N ; i++)
{
while(ST[0] >= 1 && prod(ST[ST[0] - 1], ST[ST[0]], ind[i]) < 0)// pt coliniaritate <=
ST[0]--;
ST[++ST[0]] = ind[i];
}
}
void scrie()
{
printf("%d\n",ST[0]);
for(int i = 1 ; i <= ST[0] ; i++)
printf("%lf %lf\n", X[ST[i]], Y[ST[i]]);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
citire();
sort(ind + 2, ind + N + 1, cmp);
stiva();
scrie();
return 0;
}