Pagini recente » Cod sursa (job #1418036) | Cod sursa (job #2294861) | Cod sursa (job #1724476) | Cod sursa (job #1428570) | Cod sursa (job #2877385)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define cin fin
#define cout fout
#define N 120005
struct pct
{
double x, y;
}v[N];
vector < pct > p;
double jos, stanga;
int ind, n;
double cros(pct x, pct y, pct z)
{
return (y.x-x.x)*(z.y-x.y) - (z.x-x.x)*(y.y-x.y);
}
bool cmp(pct x, pct y)
{
return (cros(v[1],x,y) < 0);
}
int main()
{
cin >> n;
jos = stanga = 1000000000;
for(int i = 1 ; i <= n ; i++)
{
cin >> v[i].x >> v[i].y;
if(v[i].y < jos)
{
jos = v[i].y;
stanga = v[i].x;
ind = i;
}
else if(v[i].y == jos)
{
if(v[i].x < stanga)
{
stanga = v[i].x;
ind = i;
}
}
}
swap(v[1],v[ind]);
sort(v+2,v+n+1,cmp);
p.push_back(v[1]);
p.push_back(v[2]);
for(int i = 3 ; i <= n ; i++)
{
while(p.size() >= 2 && cros(p[p.size()-2],p[p.size()-1],v[i]) > 0)
{
p.pop_back();
}
p.push_back(v[i]);
}
cout << p.size() << '\n';
int t = p.size();
while(t != 0)
{
cout << fixed << setprecision(9) << p[t-1].x << " " << p[t-1].y << '\n';
t--;
}
return 0;
}