Pagini recente » Cod sursa (job #1473758) | Cod sursa (job #145942) | Cod sursa (job #1546236) | Cod sursa (job #2663848) | Cod sursa (job #2756355)
#include <fstream>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <iomanip>
#define ll long long
#define Kicsi 1e-12
#define Nagy 1<<30
using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
ll n,m,i,j,poz;
struct pont
{
double x,y;
};
vector <pont> x;
pont akt={0,Nagy};
bool rendez (pont a, pont b)
{
double p=(a.x-akt.x)*(b.y-akt.y)-(b.x-akt.x)*(a.y-akt.y);
return p>Kicsi;
}
bool fordul (pont a, pont b, pont c)
{
double p=(b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
return p>Kicsi;
}
int main()
{
cin>>n;
vector <pont> x(n+1);
for (i=1;i<=n;++i)
{
cin>>x[i].x>>x[i].y;
if (x[i].y<akt.y)
{
akt=x[i];
poz=i;
}
else if (x[i].y==akt.y && x[i].x<akt.x)
{
akt=x[i];
poz=i;
}
}
x[poz]=x[1];
x[1]=akt;
sort(x.begin()+2,x.end(),rendez);
x.push_back(x[1]);
vector <pont> v(n+5);
v[1]=x[1];
v[2]=x[2];
i=2;
ll db=2;
for (i=3;i<=n+1;++i)
{
while (db>=2&&!fordul(v[db-1],v[db],x[i])) db--;
db++;
v[db]=x[i];
}
cout<<db-1<<"\n";
for (i=1;i<db;++i) cout<<setprecision(6)<<fixed<<v[i].x<<" "<<v[i].y<<"\n";
return 0;
}