Pagini recente » Cod sursa (job #1681150) | Cod sursa (job #3002024) | Cod sursa (job #722472) | Cod sursa (job #3277387) | Cod sursa (job #1989858)
#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,nxt[120100],prv[120100]; 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; });
nxt[1]=prv[1]=2;
nxt[2]=prv[2]=1;
int i;
for (i=3; i<=N; i++){
if (a[i].y>=a[i-1].y)
prv[i]=i-1,nxt[i]=nxt[i-1];
else
nxt[i]=i-1,prv[i]=prv[i-1];
prv[nxt[i]]=i,nxt[prv[i]]=i;
while (i!=nxt[nxt[i]] && area(a[i],a[nxt[i]],a[nxt[nxt[i]]])<0){
prv[nxt[nxt[i]]]=i;
nxt[i]=nxt[nxt[i]];
}
while (i!=prv[prv[i]] && area(a[prv[prv[i]]],a[prv[i]],a[i])<0){
nxt[prv[prv[i]]]=i;
prv[i]=prv[prv[i]];
}
}
vector<point> res(0);
i=N;
do{
res.push_back(a[i]);
i=nxt[i];
} while (i!=N);
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;
}