Pagini recente » Cod sursa (job #314364) | Cod sursa (job #864866) | Cod sursa (job #1824314) | Arhiva de probleme | Cod sursa (job #1174076)
#include<fstream>
#include<algorithm>
#define ll long long
#define ld long double
#define x first
#define y second
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int Nmax = 120001;
typedef pair<ld,ld> point;
point v[Nmax],S[Nmax];
int N,K;
ld cp(point A,point B,point C){return A.x*B.y - A.y*B.x + B.x*C.y - B.y*C.x + C.x*A.y - C.y*A.x;}
bool cmp(point A,point B){return cp(v[1],A,B)<0;}
int main(){
in>>N;
for(int i=1;i<=N;i++) in>>v[i].x>>v[i].y;
sort(v+1,v+N+1);
sort(v+2,v+N+1,cmp);
S[++K]=v[1];
S[++K]=v[2];
for(int i=3;i<=N;i++){
while(K>=2 && cp(S[K-1],S[K],v[i])>0) K--;
S[++K]=v[i];
}
out.precision(6);
for(int i=K;i>=1;i--) out<<fixed<<S[i].x<<' '<<S[i].y<<'\n';
return 0;
}