Pagini recente » Cod sursa (job #1433589) | Cod sursa (job #2279088) | Cod sursa (job #2094703) | Cod sursa (job #75620) | Cod sursa (job #2105948)
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
struct POINT{
long double x , y;
} point[120100];
bool cmp (POINT a , POINT b){
if (a.x == b.x){
return a.y < b.y;
}
return a.x < b.x;
}
vector <POINT> down;
vector <POINT> up;
long double det (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;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin>>n;
for (int i=1; i<=n; i++){
cin>>point[i].x>>point[i].y;
}
sort(point + 1, point + n + 1 , cmp);
for (int i=1; i<=n; i++){
while (down.size() > 1 && det(down[down.size()-2] , down[down.size()-1] , point[i]) <= 0){
down.pop_back();
}
down.push_back(point[i]);
}
for (int i=n; i>=1; i--){
while (up.size() > 1 && det(up[up.size()-2] , up[up.size()-1] , point[i]) <= 0){
up.pop_back();
}
up.push_back(point[i]);
}
cout<<down.size() + up.size() - 2<<'\n';
for (int i=0; i<down.size()-1; i++){
cout<<setprecision(12)<<fixed<<down[i].x<<" "<<down[i].y<<'\n';
}
for (int i=0; i<up.size()-1; i++){
cout<<setprecision(12)<<fixed<<up[i].x<<" "<<up[i].y<<'\n';
}
return 0;
}