Pagini recente » Cod sursa (job #1781452) | Cod sursa (job #1414458) | Cod sursa (job #1548751) | Cod sursa (job #104007) | Cod sursa (job #1723482)
#include <cstdio>
//#include <iostream>
#include <algorithm>
#define punct pair<double,double>
#define mkp make_pair
#define x first
#define y second
using namespace std;
FILE*si=fopen("infasuratoare.in","r");
FILE*so=fopen("infasuratoare.out","w");
punct v[120005];
punct inf[120005];
double det(punct a,punct b,punct c)
{
return (a.x-b.x)*(a.y-c.y)-(a.x-c.x)*(a.y-b.y);
}
bool comp(punct a,punct b)
{
return (det(v[1],a,b)>0);
}
int main()
{
int n;
fscanf(si,"%i",&n);
int i;
for(i=1;i<=n;++i)
{
fscanf(si,"%lf %lf",&v[i].x,&v[i].y);
}
for(i=2;i<=n;++i)
{
if(v[i]<v[1])
{
swap(v[i],v[1]);
}
}
sort(v+2,v+n+1,comp);
int sol=2;
inf[1]=v[1];
inf[2]=v[2];
for(i=3;i<=n;++i)
{
while(sol>=2&&(det(inf[sol-1],inf[sol],v[i])<0))
--sol;
++sol;
inf[sol]=v[i];
}
fprintf(so,"%i\n",sol);
for(i=1;i<=sol;++i)
{
//cout<<inf[i].x<<' '<<inf[i].y<<'\n';
fprintf(so,"%.6f %.6f\n",inf[i].x,inf[i].y);
}
fclose(so);
return 0;
}