Pagini recente » Cod sursa (job #898736) | Cod sursa (job #1523341) | Cod sursa (job #680144) | Cod sursa (job #2503376) | Cod sursa (job #650174)
Cod sursa(job #650174)
#include <fstream>
#include <algorithm>
#include <bitset>
#include <iomanip>
#define PDD pair<double,double>
#define st first
#define nd second
#define EPS 1e-12
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int N , H , s[12005];
PDD v[120005] , P[120005];
bitset<120005> use;
inline int cmp(const double a,const double b)
{
if(a + EPS < b) return -1;
if(b + EPS < a) return 1;
return 0;
}
struct PDD_cmp{ bool operator() (const PDD &x,const PDD &y)
const { int r = cmp(x.st,y.st);
if(r!=0) return r == -1;
return cmp(x.nd,y.nd) == -1;
};
};
int semn(PDD a, PDD b, PDD c)
{
double A = a.nd-b.nd, B = b.st-a.st, C = a.st*b.nd - b.st*a.nd;
return cmp(A * c.st + B * c.nd + C, 0);
}
void convex_hull()
{
int i = 3, pas = 1 , k = 0 ;
sort(v + 1,v + N + 1,PDD_cmp());
use[2] = true;
s[++k] = 1 , s[++k] = 2;
while(use[1] == false)
{
while(use[i])
{
if(i == N) pas = -1;
i+=pas;
}
while(k>=2 && semn(v[s[k-1]],v[s[k]],v[i]) == -1)
use[s[k--]] = 0;
s[++k] = i , use[i] = true;
}
H = k - 1;
for(i = 1;i<=H;++i)
P[i] = v[s[i]];
}
int main()
{
fin>>N;
for(int i = 1;i<=N;++i)
fin>>v[i].st>>v[i].nd;
convex_hull();
fout<<H<<'\n';
for(int i = 1;i<=H;++i)
fout<<fixed<<setprecision(6)<<P[i].st<<' '<<P[i].nd<<'\n';
return 0;
}