Pagini recente » Cod sursa (job #2323352) | Cod sursa (job #2112205) | Cod sursa (job #852542) | Cod sursa (job #2548105) | Cod sursa (job #419894)
Cod sursa(job #419894)
#include<stdio.h>
#include<algorithm>
#define inf 1000000010
#define Nmax 121000
struct punct
{
double x,y;
}a[Nmax],a0;
int n,k;
int s[Nmax];
using namespace std;
int compar(punct b,punct c)
{
return (((c.x-a[0].x)*(b.y-a[0].y)-(b.x-a[0].x)*(c.y-a[0].y))<0);
}
void functie()
{
s[0]=0;
s[1]=1;
k=1;
for(int i=2;i<n;i++)
{
while((a[i].x-a[s[k-1]].x)*(a[s[k]].y-a[s[k-1]].y)-(a[s[k]].x-a[s[k-1]].x)*(a[i].y-a[s[k-1]].y)>0 && k>1)
k--;
k++;
s[k]=i;
}
}
int main()
{
a0.x=a0.y=inf;
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
int poz;
for(int i=0;i<n;i++)
{
scanf("%lf %lf",&a[i].x,&a[i].y);
if((a0.x>a[i].x) || ((a0.x==a[i].x) && (a0.y>a[i].y)))
{ a0=a[i];
poz=i;
}
}
a[poz]=a[0];
a[0]=a0;
sort(a+1,a+n,compar);
functie();
printf("%d\n",k+1);
for(int i=0;i<=k;i++)
{
printf("%.6lf %.6lf\n",a[s[i]].x,a[s[i]].y);
}
return 0;
}