Pagini recente » Clasament dupa rating | Cod sursa (job #204547) | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #659506)
Cod sursa(job #659506)
#include<fstream>
#include<algorithm>
using namespace std;
int i,j,n,m,s[120010],poz,k;
struct puncte
{
double x,y,p;
};
puncte a[120010],b,aux;
int cmp(puncte a,puncte b)
{
if(a.p==b.p)
return a.x<b.x;
return a.p<b.p;
}
int convex()
{
puncte a1,a2,a3;
double s1;
a1=a[s[k-1]];
a2=a[s[k]];
a3=a[i];
s1=(a1.x-a3.x)*(a2.y-a1.y)+(a1.x-a2.x)*(a1.y-a3.y);
if(s1>0)
return 1;
return 0;
}
int main()
{
FILE *f=fopen("infasuratoarea.in","r");
FILE *g=fopen("infasuratoarea.out","w");
fscanf(f,"%d",&n);
b.x=b.y=1<<30;
for(i=1;i<=n;++i)
{
fscanf(f,"%lf%lf",&a[i].x,&a[i].y);
if(a[i].x<b.x||(a[i].x==b.x&&a[i].y<b.y))
b=a[i],poz=i;
}
aux=a[poz],a[poz]=a[1],a[1]=aux;
for(i=2;i<=n;++i)
a[i].p=(a[i].y-b.y)/(a[i].x-b.x);
sort(a+2,a+n+1,cmp);
s[1]=1,s[2]=2,k=2;
for(i=3;i<=n;++i)
{
while(!convex()&&k>2)
--k;
s[++k]=i;
}
fprintf(g,"%d\n",k);
for(i=1;i<=k;++i)
fprintf(g,"%.6f %.6f\n",a[s[i]].x,a[s[i]].y);
return 0;
}