Pagini recente » Cod sursa (job #861702) | Cod sursa (job #961339) | Cod sursa (job #1016828) | Cod sursa (job #836817) | Cod sursa (job #2552738)
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " <, x << "\n";
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dd;
struct point
{
dd x,y;
};
bool wecmp(point a,point b){
if(a.y == b.y)
return a.x < b.x;
return a.y < b.y;
}
vector <point> points;
vector <point> convex_hull;
int n,vf;
point stiva[120001];
bool prost(point a, point b, point c){
double rez = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
return (rez < 0);
}
int main()
{
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
cin >> n;
for(int i = 0; i < n; i++)
{
point punct;
cin >> punct.x >> punct.y;
points.push_back(punct);
}
sort(points.begin(),points.end(),wecmp);
stiva[++vf] = points[0];
stiva[++vf] = points[1];
for(int i = 2;i < n;i++){
while(vf > 1 && prost(stiva[vf-1],stiva[vf],points[i])){
vf--;
}
stiva[++vf] = points[i];
}
int i;
for(i = 1;i <= vf;i++)
convex_hull.push_back(stiva[i]);
vf = 0;
reverse(points.begin(),points.end());
stiva[++vf] = points[0];
stiva[++vf] = points[1];
for(int i = 2;i < n;i++){
while(vf > 1 && prost(stiva[vf-1],stiva[vf],points[i])){
vf--;
}
stiva[++vf] = points[i];
}
for(i = 2;i <= vf - 1;i++)
convex_hull.push_back(stiva[i]);
cout << convex_hull.size() << "\n";
for(auto x : convex_hull){
cout << fixed << setprecision(12) << x.x << " " << fixed << setprecision(12) << x.y << "\n";
}
return 0;
}