Pagini recente » Cod sursa (job #2017417) | Cod sursa (job #844891) | Cod sursa (job #1776949) | Cod sursa (job #2553578) | Cod sursa (job #1645196)
#include <iostream>
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
int i,n,st[120001],vf,poz;
struct punct
{
double x,y;
}p1,p2,p3,v[120001];
double intoarcere(punct a,punct b,punct c)
{
double x=(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
return x;
}
double compare(punct a,punct b)
{
return intoarcere(v[1],a,b)<0;
}
int main()
{
ifstream f("infasuratoare.in");f>>n;
for(i=1;i<=n;i++){f>>v[i].x>>v[i].y;}
f.close();poz=1;
for(i=2;i<=n;i++)
{
if(v[i].x==v[poz].x&&v[i].y<v[poz].y)poz=i;
else if(v[i].x<v[poz].x)poz=i;
}
p1=v[poz];v[poz]=v[1];v[1]=p1;
sort(v+2,v+1+n,compare);//for(i=1;i<=n;i++)cout<<v[i].x<<" "<<v[i].y<<'\n';
st[1]=1;st[2]=2;vf=2;
for(i=3;i<=n;i++)
{
while(vf>1&&intoarcere(v[st[vf-1]],v[st[vf]],v[i])>0)vf--;
vf++;st[vf]=i;
}
ofstream g("infasuratoare.out");g<<vf<<'\n';
for(i=vf;i>0;i--)
{
g<<fixed;
n=st[i];
g<<setprecision(12)<<v[n].x<<" "<<v[n].y<<'\n';
}
g.close();
return 0;
}