Pagini recente » Cod sursa (job #2832539) | Cod sursa (job #240660) | Cod sursa (job #247117) | Cod sursa (job #2709802) | Cod sursa (job #881433)
Cod sursa(job #881433)
#include <iostream>
#include <fstream>
#include <algorithm>
#define MAXN 120001
using namespace std;
struct point {
double x, y;
};
int n, nr;
int ch[MAXN];
point p[MAXN];
void read () {
int i;
ifstream f("infasuratoare.in");
f>>n;
for (i=1; i<=n; ++i)
f>>p[i].x>>p[i].y;
f.close();
}
bool comp (point a, point b) {
if (a.y < b.y) return true;
if (a.y > b.y) return false;
if (a.x < b.x) return true;
return false;
}
bool valid (point a, point b, point c) {
//true daca c e la dreapta dreptei ab
double d;
d = a.x*b.y + b.x*c.y + c.x*a.y - c.x*b.y - a.x*c.y - b.x*a.y;
if (d < 0) return true;
return false;
}
void convex_hull () {
ch[++nr] = 1; ch[++nr] = 2;
bool ok=0;
int i=3, k;
//pana sus
while (!ok) {
if (i==n) ok = !ok;
if (!valid(p[ch[nr-1]], p[ch[nr]], p[i])) ch[++nr] = i;
else {
k=0;
do { ch[nr-k] = i; ++k;
} while (valid(p[ch[nr-2]], p[ch[nr-1]], p[ch[nr]]));
nr -= k-1;
}
++i;
}
//inapoi jos
i-=2;
ch[++nr] = i--;
while (ok) {
if (i==1) ok = !ok;
if (valid(p[ch[nr]], p[ch[nr-1]], p[i])) ch[++nr] = i;
else {
k=0;
do { ch[nr-k] = i; ++k;
} while (valid(p[ch[nr-2]], p[ch[nr-1]], p[ch[nr]]));
nr -= k-1;
}
--i;
}
--nr;
}
void write () {
ofstream g("infasuratoare.out");
int i;
g<<nr<<'\n';
for (i=1; i<=nr; ++i)
g<<p[ch[i]].x<<' '<<p[ch[i]].y<<'\n';
g.close();
}
int main () {
read ();
sort (p, p+n+1, comp);
convex_hull ();
write ();
return 0;
}