Pagini recente » Cod sursa (job #1839736) | Cod sursa (job #2671005) | Cod sursa (job #2954050) | Cod sursa (job #2109206) | Cod sursa (job #2194746)
#include<fstream>
#include<iomanip>
#include<algorithm>
using namespace std;
ifstream in ("infasuratoare.in");
ofstream out ("infasuratoare.out");
struct punct {
double x,y;
}v[120007];
int stiva[120007],s,n,poz;
double unghi (punct a, punct b, punct c) {
return (b.x - a.x) * (c.y -a.y) - (b.y - a.y) * (c.x - a.x);
}
bool cmp (punct a, punct b) {
return unghi(v[1],a,b) < 0;
}
int main (void) {
in >> n;
for (int i = 1; i <= n; i ++) {
in >> v[i].x >> v[i].y;
}
poz = 1;
for (int i = 1; i <= n; i ++) {
if (v[poz].x > v[i].x) {
poz = i;
}
if (v[poz].x == v[i].x) {
if (v[poz].y > v[i].y) {
poz = i;
}
}
}
swap (v[poz], v[1]);
sort (v+2,v+n+1,cmp);
stiva[1] = 1;
s = 1;
stiva[2] = 2;
s = 2;
for (int i = 3; i <= n; i ++) {
while (s > 2 && unghi(v[stiva[s-1]], v[stiva[s]], v[i]) > 0) {
s --;
}
s ++;
stiva[s] = i;
}
out << s <<"\n";
for (int i = s; i >= 1; i --) {
out << setprecision(9) << fixed << v[stiva[i]].x <<" "<<v[stiva[i]].y <<"\n";
}
return 0;
}