Pagini recente » Cod sursa (job #2457137) | Cod sursa (job #1370530) | Cod sursa (job #1197314) | Cod sursa (job #3154117) | Cod sursa (job #1989831)
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <iomanip>
using namespace std;
#define fi first
#define se second
typedef long long LL;
typedef long double LD;
struct point{
LD x,y;
};
int N; point a[120100];
LD area(point A, point B, point C){
return (A.x*B.y+B.x*C.y+C.x*A.y-A.y*B.x-B.y*C.x-C.y*A.x);
}
vector<point> gethull(){
sort(a+1,a+N+1,[](point A, point B) { return A.x < B.x; });
point dhull[130000],uhull[130000];
point cr=a[1];
int i,usz=0,dsz=0;
for (i=2; i<=N; i++){
if (cr.y>=a[i].y) uhull[++usz]=cr;
else dhull[++dsz]=cr;
cr=a[i];
while (usz>1 && area(cr,uhull[usz],uhull[usz-1])<=0) usz--;
while (dsz>1 && area(cr,dhull[dsz],dhull[dsz-1])>=0) dsz--;
}
vector<point> res(0);
for (i=1; i<=dsz; i++)
res.push_back(dhull[i]);
res.push_back(cr);
for (i=usz; i>0; i--)
res.push_back(uhull[i]);
return res;
}
int main(){
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
fin >> N;
int i;
for (i=1; i<=N; i++)
fin >> a[i].x >> a[i].y;
vector<point> ans(0);
ans = gethull();
fout << fixed << setprecision(9);
fout << ans.size() << "\n";
for (point P : ans)
fout << P.x << " " << P.y << "\n";
return 0;
}