Pagini recente » Cod sursa (job #1399415) | Cod sursa (job #2025223) | Cod sursa (job #341242) | Cod sursa (job #946223) | Cod sursa (job #719774)
Cod sursa(job #719774)
#include <fstream>
#include <algorithm>
using namespace std;
#define lung 200000
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point {
long double x, y;
};
int stiva[lung], ps = 1, n, v[lung];
point p[lung];
bool cmp(int i, int j) {
return (long double)(p[i].x - p[ps].x) * (p[j].y - p[ps].y) < (long double)(p[j].x - p[ps].x) * (p[i].y - p[ps].y);
}
long double semn(int i1, int i2, int i3)
{
return (long double)p[i1].x * p[i2].y + p[i2].x * p[i3].y + p[i3].x * p[i1].y - p[i1].y * p[i2].x - p[i2].y * p[i3].x - p[i3].y * p[i1].x;
}
int main() {
int i;
fin >> n;
for (i = 1; i <= n; ++i) {
fin >> p[i].x >> p[i].y;
if (p[i].x < p[ps].x || (p[i].x == p[ps].x && p[i].y < p[ps].y))
ps = i;
}
for (i = 1; i <= n; ++i) {
if (i == ps) continue;
v[++v[0]] = i;
}
sort(v + 1, v + v[0] + 1, cmp);
stiva[++stiva[0]] = ps;
for (i = 1; i < n; ++i) {
if (stiva[0] >= 2 && (semn(stiva[stiva[0] - 1], stiva[stiva[0]], v[i]) > 0)) --stiva[0];
stiva[++stiva[0]] = v[i];
}
fout << stiva[0] << "\n";
for(i = 1; i <= stiva[0]; ++i)
fout << p[stiva[i]].x << " " << p[stiva[i]].y << "\n";
fout.close();
return 0;
}