Pagini recente » Cod sursa (job #1596805) | Cod sursa (job #184129) | Cod sursa (job #1098419) | Cod sursa (job #393579) | Cod sursa (job #1821248)
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <iomanip> //pentru zecimale, setprecision se combina cu fixed
using namespace std;
ifstream fin("infasuratoarea.in");
ofstream fout("infasuratoarea.out");
int n,i,j,poz,ok;
//bool viz[120010];
struct date
{
long double x,y;
} v[120110],codi[120110];
long double nebunieunghiularaparametricadeneinteles(date a, date b, date c)
{
return (c.x-a.x)*(b.y-a.y)-(c.y-a.y)*(b.x-a.x);
}
bool cmp(date a,date b)
{
return nebunieunghiularaparametricadeneinteles(v[1],a,b)>0;
/*if(a.x==b.x)
return a.y<b.y;
return a.x<b.x;*/
}
int main()
{
fin>>n;
for(i=1;i<=n;++i)
{
fin>>v[i].x>>v[i].y;
}
/*poz=1;
for(i=2;i<=n;++i)
{
if(v[i].x<v[poz].x)
poz=i;
else
{
if(v[i].x==v[poz].x)
if(v[i].y<v[poz].y)
poz=i;
}
}
swap(v[1],v[poz]);
sort(v+2,v+n+1,cmp);*/
codi[1].x=v[1].x;
codi[1].y=v[1].y;
codi[2].x=v[2].x;
codi[2].y=v[2].y;
ok=2;
for(i=3;i<=n;++i)
{
while(ok>=2 && nebunieunghiularaparametricadeneinteles(codi[ok-1],codi[ok],v[i])<0)
{
//fout<<"da\n";
--ok;
}
++ok;
codi[ok].x=v[i].x;
codi[ok].y=v[i].y;
}
fout<<ok<<"\n";
fout<<fixed<<setprecision(6);
for(i=ok;i>=1;--i)
{
fout<<codi[i].x<<" "<<codi[i].y<<"\n";
}
/*fout<<"\n";
for(i=1;i<=n;++i)
{
fout<<v[i].x<<" "<<v[i].y;
fout<<"\n";
}
//fout<<cmp(v[4],v[1]);*/
return 0;
}