Pagini recente » Cod sursa (job #2744800) | Cod sursa (job #1239214) | Cod sursa (job #1274705) | Cod sursa (job #937443) | Cod sursa (job #3195721)
#include <bits/stdc++.h>
using namespace std;
const int nmax=12e4;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct point {
double x,y;
};
vector<point>hull;
vector<point>pts(nmax+3);
int n;
int findStartPoint() {
int rez=0;
double minny=1e9,maxxx=0;
for(int i=1; i<n; i++) {
if(pts[i].y<minny) {
minny=pts[i].y;
maxxx=pts[i].x;
rez=i;
} else if(pts[i].y==minny) {
if(pts[i].x>maxxx) {
maxxx=pts[i].x;
rez=i;
}
}
}
return rez;
}
double orient(point a,point b,point c) {
return (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
}
bool cmp(point a,point b) {
return orient(pts[0],a,b)<0;
}
void createConvexHull() {
hull.push_back(pts[0]);
hull.push_back(pts[1]);
for(int i=2; i<n; i++) {
while(hull.size()>=2&&orient(hull[hull.size()-2],hull[hull.size()-1],pts[i])>=0)
hull.pop_back();
hull.push_back(pts[i]);
}
}
int main() {
cin>>n;
for(int i=0; i<n; i++)
cin>>pts[i].x>>pts[i].y;
swap(pts[0],pts[findStartPoint()]);
sort(pts.begin()+1,pts.begin()+n,cmp);
createConvexHull();
cout << setprecision(6) << fixed;
cout<<hull.size()<<"\n";
for(auto punctuletz:hull){
cout<<punctuletz.x<<" "<<punctuletz.y<<"\n";
}
return 0;
}