Pagini recente » Cod sursa (job #1974262) | Cod sursa (job #2173256) | Cod sursa (job #2507349) | Cod sursa (job #2320022) | Cod sursa (job #3148699)
#include <bits/stdc++.h>
#define cin in
#define cout out
#define double long double
using namespace std;
const string file_name("infasuratoare");
ifstream in(file_name + ".in");
ofstream out(file_name + ".out");
struct Point{
double x,y;
} v[150005], aux;
int n, vf, pos,s[150005];
double xmin, ymin = LLONG_MAX;
int comp(Point a, Point b){
return a.x * b.y >= b.x * a.y;
}
bool convex (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 ()
{
cin>>n;
for (int i = 1 ; i <= n ; i++)
{
cin>>v[i].x>>v[i].y;
if (ymin > v[i].y)
{
xmin = v[i].x;
ymin = v[i].y;
pos = i;
}
}
for (int i = 1 ; i <= n ; i++)
{
v[i].x -= xmin;
v[i].y -= ymin;
}
swap(v[1],v[pos]);
sort (v+2, v+n+1, comp);
s[1] = 1;
s[2] = 2;
vf = 2;
for (int i = 3 ; i <= n ; i++)
{
while ( vf >= 3 and !convex(v[s[vf-1]], v[s[vf]], v[i]) )
vf --;
s[++vf] = i;
}
cout<<vf<<'\n';
for (int i = 1 ; i <= vf ; i++)
cout<<fixed<<setprecision(10)<<v[s[i]].x + xmin<<' '<<v[s[i]].y + ymin<<'\n';
return 0;
}