Pagini recente » Cod sursa (job #1046764) | Cod sursa (job #1589065) | Cod sursa (job #1954808) | Cod sursa (job #3252264) | Cod sursa (job #1703537)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstdio>
//#include <iomanip>
#define pct pair<double,double>
using namespace std;
FILE* si=fopen("infasuratoare.in","r");
FILE* so=fopen("infasuratoare.out","w");
//ifstream si("infasuratoare.in");
//ofstream so("infasuratoare.out");
const int NMAX=120005;
pct v[NMAX];
pct sol[NMAX];
double det(pct a,pct b,pct c)
{
return (a.first-b.first)*(a.second-c.second)-(a.first-c.first)*(a.second-b.second);
}
bool cmp(pct a,pct b)
{
return (det(v[0],a,b)>0);
}
int main()
{
int n;
fscanf(si,"%i",&n);
int i;
for(i=0;i<n;++i)
{
fscanf(si,"%lf %lf",&v[i].first,&v[i].second);
}
for(i=1;i<n;++i)
{
if(v[i]<v[0])
{
swap(v[i],v[0]);
}
}
sort(v+1,v+n,cmp);
int nr=1;
sol[0]=v[0];
for(i=1;i<n;++i)
{
while(nr>=2&&det(sol[nr-2],sol[nr-1],v[i])<0)--nr;
sol[nr]=v[i];
++nr;
}
fprintf(so,"%i\n",nr);
for(i=1;i<nr;++i)
fprintf(so,"%f %f\n",sol[i].first,sol[i].second);
fprintf(so,"%f %f\n",sol[0].first,sol[0].second);
return 0;
}