Pagini recente » Cod sursa (job #59418) | Cod sursa (job #2534296) | Cod sursa (job #3149847) | Cod sursa (job #1399089) | Cod sursa (job #2552719)
#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 operator < (const point a)const
{
if(x != a.x)
return x < a.x;
else
return y < a.y;
}
};
vector <point> points;
set <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 * (a.y - c.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());
stiva[++vf] = points[0];
stiva[++vf] = points[1];
for(int i = 2;i < n;i++){
while(vf > 1 && prost(stiva[vf],stiva[vf - 1],points[i])){
vf--;
}
stiva[++vf] = points[i];
}
while(vf){
convex_hull.insert(stiva[vf]);
vf--;
}
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],stiva[vf - 1],points[i])){
vf--;
}
stiva[++vf] = points[i];
}
while(vf){
convex_hull.insert(stiva[vf]);
vf--;
}
cout << convex_hull.size() << "\n";
for(auto x : convex_hull){
cout << fixed << setprecision(12) << x.x << " " << fixed << setprecision(12) << x.y << "\n";
}
return 0;
}