Pagini recente » Cod sursa (job #153256) | Cod sursa (job #2926964) | Cod sursa (job #163466) | Cod sursa (job #1697028) | Cod sursa (job #2718037)
/**
Konvex burkolo
Kivalasztom a legalso elemet, azok kozul is a legbaloldalibbat. Utana a tobbi elemet rendezem a szog szerint, amit
a legalso elem egyenesevel zar be. Ezt ugy csinalom, hogy a legalso elemet kitcserelem az elsovel, mert ugyis az kell
legyen az elso, es a tobbit sortolom. A sort-hoz hasznalom a fgv1-et, ami megmondja, hogy az elso elem, es az akt1 elem
altal letrehozott egyenestol az akt2 az jobbra vagy balra van.
Ezutan csinalom meg a konvex burkolot, hasonlo rendszer szerint haladva> ha az elozo ket pont altal alkotott egyeneshez kepest
az aktualis pont balra van, akkor beteszem a vegere, ha nem, akkor addig veszem az eloso ket part a burkolobol, amig rendben nem lesz.
**/
#include <fstream>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <iomanip>
using namespace std;
#define NAGY 1<<30
#define KICSI 1e-12
#define P pair<double,double>
#define x first
#define y second
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
P a={0,NAGY};
int n,k,i,j,bur,h;
bool fgv1(P r, P p)
{
int f=0;
double cr=(r.x-a.x)*(p.y-a.y)-(p.x-a.x)*(r.y-a.y);
return cr>KICSI;
}
bool fgv(P q, P r, P p)
{
int f=0;
double cr=(r.x-q.x)*(p.y-q.y)-(p.x-q.x)*(r.y-q.y);
return cr>KICSI;
}
int main()
{
cin>>n;
vector<P>x(n+1);
for(i=1;i<=n;i++)
{
cin>>x[i].x>>x[i].y;
if(x[i].y<a.y)
{
h=i;
a=x[i];
}
else if(x[i].y==a.y && x[i].x<a.x)
{
h=i;
a=x[i];
}
}
x[h]=x[1];
x[1]=a;
sort(x.begin()+2,x.end(),fgv1);
x.push_back(x[1]);
vector<P>v(n+5);
v[1]=x[1];
v[2]=x[2];
i=2;
j=3;
bur=2;
for(i=3;i<=n+1;++i)
{
while(bur>2 && !fgv(v[bur-1],v[bur],x[i])) --bur;
++bur;
v[bur]=x[i];
}
cout<<bur-1<<"\n";
for(i=1;i<bur;++i) cout<<setprecision(6)<<fixed<<v[i].x<<" "<<v[i].y<<"\n";
return 0;
}