Pagini recente » Cod sursa (job #160159) | Cod sursa (job #800913) | Cod sursa (job #1240920) | Cod sursa (job #1787947) | Cod sursa (job #1370537)
#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++)
{
scanf("%lf %lf", &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++)
{
while(area(li[sol[s-2]], li[sol[s-1]], li[i]) > 0 && s>2)
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;
}