Pagini recente » Cod sursa (job #2009787) | Cod sursa (job #529846) | Cod sursa (job #1224831) | Cod sursa (job #1557244) | Cod sursa (job #744883)
Cod sursa(job #744883)
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
#define x first
#define y second
typedef pair<double, double>Point;
const int NMAX = 120005;
const double EPS = 1e-12;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
Point v[NMAX];
bool viz[NMAX];
int st[NMAX],n;
void read(){
fin>>n;
for(int i=1;i<=n;++i)fin>>v[i].x>>v[i].y;
}
double det(Point x1,Point x2,Point x3){
return (x2.x - x1.x) * (x3.y - x1.y) - (x3.x - x1.x) * (x2.y - x1.y);
}
void convex_hull(){
int vf = 2,p;
sort(v+1,v+n+1);
st[1] = 1; st[2] = 2;
viz[2] = 1; p = 1;
int i = 1;
while(i>0){
if(!viz[i]){
while(vf >=2 && det(v[st[vf-1]],v[st[vf]],v[i])< EPS )
viz[st[vf--]] = 0;
st[++vf] = i;
viz[i] = 1;
}
if(i==n)p=-p;
i+=p;
}
fout<<vf-1<<'\n';
fout<< setprecision(6) << fixed;
for(int i=1;i<vf;++i)
fout<<v[st[i]].x<<' '<<v[st[i]].y<<'\n';
}
int main(void){
read();
convex_hull();
return 0;
}