Pagini recente » Cod sursa (job #2099838) | Cod sursa (job #1717960) | Cod sursa (job #2049289) | Cod sursa (job #2761276) | Cod sursa (job #2287597)
#include <fstream>
#include <algorithm>
#include <climits>
#include <iomanip>
#define MAX 120100
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
int vf;
struct pt{
double x, y;
}minim, p[MAX], st[MAX];
int pozmin;
bool cmp(pt a, pt b);
double CP(pt a, pt b, pt c)
{
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
bool m(pt a)
{
if(a.x < minim.x) return 1;
if(a.x == minim.x)
if(a.y < minim.y) return 1;
return 0;
}
int main()
{int i;
minim.x = INT_MAX;
minim.y = INT_MAX;
fin >> n;
for(i=1;i<=n;i++)
{
fin>>p[i].x;
fin>>p[i].y;
if(m(p[i]))
{
minim = p[i];
pozmin = i;
}
}
swap(p[1], p[pozmin]);
sort(1 + p, 1 + p + n, cmp);
/*for(i=1;i<=n;i++)
fout<<p[i].x<<' '<<p[i].y<<'\n';*/
vf = 2;
st[1] = p[1];
st[2] = p[2];
for (int i = 2; i <= n; i++) {
while (vf > 2 && CP(st[vf - 1], st[vf], p[i]) >= 0)
vf--;
st[++vf] = p[i];
}
fout << fixed;
fout << setprecision(6);
fout << vf << '\n';
for (int i = 1; i <= vf; i++)
fout << st[i].x << ' ' << st[i].y << '\n';
return 0;
}
bool cmp(pt a, pt b)
{
return CP(p[1], a, b) < 0;
}