Pagini recente » Cod sursa (job #225459) | Cod sursa (job #1538171) | Cod sursa (job #2907600) | Cod sursa (job #1752881) | Cod sursa (job #1632320)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
double x,y;
}p[120005];
int n,vf,s[120005];
inline double det(punct a,punct b,punct c)
{
return (c.x-a.x)*(b.y-a.y)-(c.y-a.y)*(b.x-a.x);
}
inline bool cmp(punct a,punct b)
{
return det(a,b,p[1])>0;
}
int main()
{
fin>>n;
int i,poz=1;
for(i=1;i<=n;i++)
{
fin>>p[i].x>>p[i].y;
if(p[poz].x>p[i].x || (p[poz].x==p[i].x && p[poz].y>p[i].y))
poz=i;
}
swap(p[1],p[poz]);
sort(p+2,p+n+1,cmp);
s[++vf]=1;s[++vf]=2;
for(i=3;i<=n;i++)
{
while(vf>=2 && det(p[s[vf-1]],p[s[vf]],p[i])<0)
vf--;
s[++vf]=i;
}
fout<<vf<<'\n';
for(i=vf;i>=1;i--)
fout<<setprecision(6)<<fixed<<p[s[i]].x<<" "<<p[s[i]].y<<'\n';
return 0;
}