Pagini recente » Cod sursa (job #2717293) | Cod sursa (job #2869497) | Cod sursa (job #49760) | Cod sursa (job #1537622) | Cod sursa (job #2375071)
#include <bits/stdc++.h>
#define Point pair<double, double>
#define x first
#define y second
#define NMAX 120001
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
inline double det(Point O, Point A, Point B){
return (A.x - O.x)*(B.y - O.y) - (B.x - O.x)*(A.y - O.y);
}
int stiva[NMAX];
Point v[NMAX];
bool comp(Point A, Point B){
return det(v[1], A, B)>0;
}
int main()
{ int n;
fin>>n>>v[1].x>>v[1].y;
for(int i=2; i<=n; i++){
fin>>v[i].x>>v[i].y;
if(v[i]<v[1]) swap(v[i], v[1]);
}
sort(v+2, v+n+1, comp);
int head=0;
for(int i=1; i<=n; i++){
while(head>=2 && det(v[stiva[head-1]], v[stiva[head]], v[i])< 0) --head;
stiva[++head] = i;
}
fout<<head<<endl;
fout<<setprecision(6)<<fixed;
for(int i=1; i<=head; i++) fout<<v[stiva[i]].x<<" "<<v[stiva[i]].y<<endl;
}