Pagini recente » Borderou de evaluare (job #1058105) | Borderou de evaluare (job #1906935) | Borderou de evaluare (job #2541977) | Borderou de evaluare (job #633691) | Cod sursa (job #2870105)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct puncte{
double x,y;
}v[105],q[105];
double produs(puncte a,puncte b,puncte c)
{
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
bool cmp(puncte b,puncte c)
{
return produs(v[1],b,c)<0;
}
int n,i,poz,vf;
int main()
{
f>>n;
for(i=1;i<=n;i++)
{
f>>v[i].x>>v[i].y;
}
poz=1;
for(i=2;i<=n;i++)
{
if(v[i].x<v[poz].x||(v[i].x==v[poz].x&&v[i].y<v[poz].y))
poz=i;
}
swap(v[poz],v[1]);
sort(v+2,v+n+1,cmp);
vf=2;
q[1]=v[1];
q[2]=v[2];
for(i=3;i<=n;i++)
{
while(vf>=2&&produs(q[vf-1],q[vf],v[i])>0)
{
vf--;
}
vf++;
q[vf]=v[i];
}
g<<vf<<'\n';
g<<q[1].x<<" "<<q[1].y<<'\n';
for(i=vf;i>=1;i--)
g<<q[i].x<<" "<<q[i].y<<'\n';;
return 0;
}