Pagini recente » Cod sursa (job #2719425) | Cod sursa (job #789734) | Cod sursa (job #3156402) | Cod sursa (job #1935113) | Cod sursa (job #1370512)
#include <bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define s sol.size()
using namespace std;
vector <pair<double, double> >li;
int n;
double a, b, x=1000006, y=1000006;
vector <int> sol;
double area(pair<double, double> a, pair<double, double> b, pair<double, double> c)
{
return a.x*b.y + b.x*c.y + a.y*c.x - c.x*b.y - b.x*a.y - a.x*c.y;
}
class compare
{
public:
bool operator()(const pair<double, double> &a, const pair<double, double> &b)
{
pair <double, double> p;
p.x=x;
p.y=y;
if(a!=p && b!=p)
return (a.y-y)/(a.x-x) > (b.y-y)/(b.x-x);
else if(a==p) return true;
else return false;
}
};
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>a>>b;
li.pb({a, b});
if(x>a)
x=a,y=b;
if(x==a && y<b)
y=b;
}
sort(li.begin(), li.end(), compare());
sol.pb(0);
sol.pb(1);
for(int i=2;i<n;i++)
{
if(area(li[sol[s-2]], li[sol[s-1]], li[i])>0)
sol.pop_back();
sol.pb(i);
}
cout<<s<<'\n';
for(int i=s-1;i>=0;i--)
{
printf("%.12f %.12f\n", li[sol[i]].x,li[sol[i]].y);
}
return 0;
}