Pagini recente » Cod sursa (job #535777) | Cod sursa (job #1371991) | Cod sursa (job #2343793) | Cod sursa (job #2396701) | Cod sursa (job #303272)
Cod sursa(job #303272)
#include <stdio.h>
#include <algorithm>
#define N 120010
using namespace std;
struct punct
{
double x,y;
}p,sir[N];
int ind[N],num,poz,n,m;
double fct(punct a,punct b)
{
return (a.x-p.x)*(b.y-p.y)-(a.y-p.y)*(b.x-p.x)>0;
}
double fct2(punct p,punct a,punct b)
{
return (a.x-p.x)*(b.y-p.y)-(a.y-p.y)*(b.x-p.x)>0;
}
bool cmf(punct a,punct b)
{
return fct(a,b)>0;
}
void citire()
{
freopen ("infasuratoare.in","r",stdin);
freopen ("infasuratoare.out","w",stdout);
scanf ("%d",&n);
scanf ("%lf %lf",&p.x,&p.y);
sir[0]=p;
for (int i=1;i<n;i++)
{
scanf ("%lf %lf",&sir[i].x,&sir[i].y);
if (sir[i].y<p.y || (sir[i].y==p.y && sir[i].x<p.x))
{
p=sir[i];
poz=i;
}
}
}
int main()
{
citire();
punct aux=sir[poz];
sir[poz]=sir[0];
sir[0]=aux;
sort(sir+1,sir+n+1,cmf);
ind[1]=0;
ind[2]=1;
int m=2;
for (int i=2;i<n;i++)
{
while (m>=2 && fct2(sir[ind[m]],sir[i],sir[ind[m-1]])<=0)
m--;
ind[++m]=i;
}
printf("%d\n",m);
for (int i=1;i<=m;i++)
printf("%lf %lf\n",sir[ind[i]].x,sir[ind[i]].y);
return 0;
}