Pagini recente » Cod sursa (job #74767) | Cod sursa (job #533294) | Cod sursa (job #369950) | Cod sursa (job #850039) | Cod sursa (job #1096141)
#include<iostream>
#include<fstream>
#include<stack>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct pct {
double x, y;
};
int n, i, poz;
pct v[120001], sol[120001], aux, mini{999999999, 999999999};
double CrossProduct(pct A, pct B, pct C) {
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
bool cmp(pct a, pct b) {
if(CrossProduct(v[0], a, b) < 0) {
return false;
}
return true;
}
int main() {
fin >> n;
for(i = 0; i < n; i++) {
fin >> v[i].x >> v[i].y;
if(v[i].x <= mini.x) {
mini = v[i];
poz = i;
}
}
aux = v[0];
v[0] = v[poz];
v[poz] = aux;
sort(v+1, v+n, cmp);
sol[0] = v[0];
sol[1] = v[1];
int nr = 1;
for(i = 2; i < n; i++) {
while(CrossProduct(sol[nr-1], sol[nr], v[i]) < 0) {
nr--;
}
nr++;
sol[nr] = v[i];
}
fout << nr + 1 << '\n';
for(i = 0; i <= nr; i++) {
fout << fixed << setprecision(6) << sol[i].x << ' ' << sol[i].y << '\n';
}
fin.close();
fout.close();
return 0;
}