Pagini recente » Cod sursa (job #1590092) | Cod sursa (job #1570053) | Cod sursa (job #2864628) | Cod sursa (job #825512) | Cod sursa (job #984774)
Cod sursa(job #984774)
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <utility>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
pair <int,int> x,y;
struct point
{
double x,y;
}v[120001];
int n,i,k,p,s[120001],t,j;
double eps=1e-12;
inline double det (const point &A, const point &B, const point &C)
{
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
inline bool cmp (const point &A, const point B)
{
return det (v[1],A,B) < 0;
}
int main ()
{
fin>>n;
for (i=1;i<=n;i++)
fin>>v[i].x>>v[i].y;
int mini=1;
for (int i=2; i<=n; ++i)
{
if (fabs(v[i].x - v[mini].x) > eps) {if (v[i].x < v[mini].x) mini=i;}
else if (v[i].y < v[mini].y) mini=i;
}
point temp = v[1];
v[1]=v[mini];
v[mini]=temp;
sort (v+2,v+n+1,cmp);
s[1]=1;
s[2]=2;
k=2;
for (i=3; i<=n; ++i)
{
while (k>=2 && det(v[s[k-1]],v[s[k]],v[i]) > 0) k--;
s[++k]=i;
}
fout<<k<<"\n";
fout<<fixed;
fout<<v[s[1]].x<<" "<<v[s[1]].y<<"\n";
for (i=k; i>1; --i) fout<<v[s[i]].x<<" "<<v[s[i]].y<<"\n";
}