Pagini recente » Cod sursa (job #129972) | Cod sursa (job #2351882) | Cod sursa (job #89919) | Cod sursa (job #2083075) | Cod sursa (job #3030329)
#include <fstream>
#include <algorithm>
#include <iomanip>
const int NMAX=120005;
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
typedef long double ld;
ld det(ld, ld, ld, ld, ld, ld);
void infasuratoare();
struct punct
{
ld x, y;
}v[NMAX], s[NMAX], pct;
bool cmp(punct, punct);
int n;
int main()
{
int i;
fin>>n;
for(i=1; i<=n; i++) fin>>v[i].x>>v[i].y;
infasuratoare();
return 0;
}
void infasuratoare()
{
int i, cnt=0, poz;
pct.x=pct.y=1e9;
for(i=1; i<=n; i++)
{
if(v[i].y<pct.y)
{
pct=v[i];
poz=i;
}
else if(v[i].y==pct.y && v[i].x<pct.x)
{
pct=v[i];
poz=i;
}
}
swap(v[1], v[poz]);
sort(v+2, v+n+1, cmp);
s[++cnt]=v[1];
s[++cnt]=v[2];
for(i=3; i<=n; i++)
{
while(cnt>=2 && det(v[i].x, v[i].y, s[cnt-1].x, s[cnt-1].y, s[cnt].x, s[cnt].y)>0)
{
cnt--;
}
s[++cnt]=v[i];
}
fout<<cnt<<'\n';
for(i=cnt; i>=1; i--) fout<<fixed<<setprecision(10)<<s[i].x<<' '<<s[i].y<<'\n';
}
bool cmp(punct a, punct b)
{
return(det(b.x, b.y, v[1].x, v[1].y, a.x, a.y)<0);
}
ld det(ld x3, ld y3, ld x1, ld y1, ld x2, ld y2)
{
return x1*(y2-y3)-y1*(x2-x3)+(x2*y3-y2*x3);
}