Pagini recente » Cod sursa (job #1983890) | Cod sursa (job #1514213) | Cod sursa (job #713449) | Cod sursa (job #1497766) | Cod sursa (job #650176)
Cod sursa(job #650176)
#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;
};
};
static int ccw(const PDD &a,const PDD &b,const PDD &c)
{
double area2 = (b.st-a.st)*(c.nd-a.nd) - (b.nd-a.nd)*(c.st-a.st);
return cmp(area2,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 && ccw(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;
}