Pagini recente » Cod sursa (job #1744299) | Cod sursa (job #2394433) | Istoria paginii runda/abcabc/clasament | Istoria paginii runda/simulare_oji_2023_clasa_9_17_martie/clasament | Cod sursa (job #302362)
Cod sursa(job #302362)
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define Nmax 121100
#define Inf 0x3f3f3f3f
double x[Nmax],y[Nmax];
int st[Nmax];
int n,poz,k;
int a[Nmax];
inline bool comp(int i,int j)
{
return (x[i]-x[poz])*(y[j]-y[poz])<(x[j]-x[poz])*(y[i]-y[poz]);
}
double arie(int a, int b, int c)
{
return x[a]*y[b]+x[b]*y[c]+x[c]*y[a]-y[b]*x[c]-y[c]*x[a]-y[a]*x[b];
}
int main()
{
int i,j;
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d\n", &n);
for (i=1;i<=n;++i)
scanf("%lf %lf", &x[i], &y[i]);
poz=0;
x[poz]=Inf;
y[poz]=Inf;
for (i=1;i<=n;++i)
if ((x[i]<x[poz]) || (x[i]==x[poz] && y[i]<y[poz]))
{
poz=i;
}
for (i=1;i<=n;++i)
if(i!=poz)
a[++a[0]]=i;
sort(a+1,a+a[0]+1,comp);
st[++k]=poz;
st[++k]=a[0];
for (i=1;i<=a[0];++i)
{
while(k>1 && arie(st[k-1],st[k],a[i])>0)
k--;
st[++k]=a[i];
}
printf("%d\n", k);
for (i=k;i>=1;--i)
printf("%.6lf %.6lf\n", x[st[i]],y[st[i]]);
return 0;
}