Pagini recente » Cod sursa (job #652310) | Cod sursa (job #927046) | Cod sursa (job #1463701) | Cod sursa (job #841577) | Cod sursa (job #560652)
Cod sursa(job #560652)
#include <fstream>
#include <algorithm>
#include <math.h>
#include <iomanip>
#define nmax 120005
#define maxx 100000
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
int init;
double x[nmax], y[nmax];
int v[nmax];
int s[nmax];
bool cmp(int i, int j)
{
return (double) (x[i] - x[init]) * (y[j] - y[init]) < (double) (x[j] - x[init]) * (y[i] - y[init]);
}
long double det(int i1, int i2, int i3)
{
return (long double) x[i1] * y[i2] + x[i2] * y[i3] + x[i3] * y[i1] - y[i1] * x[i2] - y[i2] * x[i3] - y[i3] * x[i1];
// > la dreapta
// < stanga
}
int main()
{
int i;
fin >> n;
init = 0;
x[init] = y[init] = maxx;
for(i = 1; i <= n; ++ i)
{
fin >> x[i] >> y[i];
if(x[i] < x[init] || (x[i] == x[init] && y[i] < y[init]))
init = i;
}
for(i = 1; i <= n; ++ i)
{
if(i == init) continue;
v[++v[0]] = i;
}
sort(v + 1, v + v[0] + 1, cmp);
s[0] = 1;
s[s[0]] = init;
for(i = 1; i <= v[0]; ++ i)
{
if(init == v[i]) continue;
while(det(s[s[0] - 1], s[s[0]], v[i]) > 0 && s[0] >= 2) --s[0];
s[++s[0]] = v[i];
}
s[++s[0]] = init;
fout << fixed << setprecision(6);
fout << s[0] - 1 << "\n";
reverse(s + 1, s + s[0] + 1);
for(i = 1; i < s[0]; ++i)
fout << x[s[i]] << " " << y[s[i]] << "\n";
return 0;
}