Pagini recente » Cod sursa (job #1729915) | Cod sursa (job #2583938) | Cod sursa (job #1726542) | Cod sursa (job #2628526) | Cod sursa (job #2809827)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int N = 1.2e5 + 1;
int n, varf, stiva[N];
pair<double, double> p[N];
bool vis[N];
inline double produsIncrucisat(pair<double, double> A, pair<double, double> B, pair<double, double> C){
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x); // valoarea componentei pe axa z a lui AB X AC
}
int main(){
f >> n;
for(int i = 1; i <= n; i++)
f >> p[i].x >> p[i].y;
f.close();
sort(p + 1, p + n + 1);
stiva[1] = 1;
stiva[2] = 2;
varf = 2;
vis[1] = vis[2] = 1;
for(int i = 3, k = 1; i > 0; i += (k = (i == n ? -k : k))){ // mergem de la 1 la n (sub dreapta), apoi de la n la 0 (peste dreapta)
if(vis[i])
continue;
while(varf >= 2 && produsIncrucisat(p[stiva[varf - 1]], p[stiva[varf]], p[i]) < 1e-12)
vis[stiva[varf--]] = 0;
stiva[++varf] = i;
vis[i] = 1;
}
g << fixed << setprecision(9) << varf << '\n';
for(int i = 1; i <= varf; i++)
g << p[stiva[i]].x << ' ' << p[stiva[i]].y << '\n';
g.close();
}