Pagini recente » Cod sursa (job #854798) | Cod sursa (job #2904232) | Cod sursa (job #1276445) | Cod sursa (job #1293987) | Cod sursa (job #801468)
Cod sursa(job #801468)
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
struct point{double x,y;};
int n,i,j,st[120000],kk;
point v[120000],mn,aux;
bool cmp(point a,point b)
{
return ((a.y-mn.y)*(b.x-mn.x)<=(a.x-mn.x)*(b.y-mn.y));
}
bool smn(point a,point b,point c)
{
double s;
s=(long double)a.x*b.y+b.x*c.y+c.x*a.y-a.y*b.x-b.y*c.x-c.y*a.x;
if (s<=0) return 0;
if (s>0) return 1;
}
FILE *f=fopen("infasuratoare.in","r");
FILE *g=fopen("infasuratoare.out","w");
int main()
{
fscanf(f,"%d",&n);
fscanf(f,"%lf%lf",&v[1].x,&v[1].y);
mn=v[1];
for (i=2;i<=n;i++)
{
fscanf(f,"%lf%lf",&v[i].x,&v[i].y);
if (v[i].x<mn.x){
mn=v[i];
kk=i;}
else if (v[i].x==mn.x )
if (v[i].y>mn.y){ mn=v[i];kk=i;}
}
aux=v[1];
v[1]=mn;
v[kk]=aux;
sort(v+2,v+n+1,cmp);
st[0]=2;
st[1]=1;
st[2]=2;
i=1;
for (i=3;i<=n;i++)
{
while (!smn(v[st[st[0]-1]],v[st[st[0]]],v[i])&& st[0]>=1) st[0]--;
st[0]++;
st[st[0]]=i;
}
fprintf(g,"%d\n",st[0]);
for (i=1;i<=st[0];i++) fprintf(g,"%.6lf %.6lf\n",v[st[i]].x,v[st[i]].y);
return 0;
}