Pagini recente » Cod sursa (job #2407121) | Cod sursa (job #2434497) | Cod sursa (job #606313) | Cod sursa (job #1253444) | Cod sursa (job #2468456)
#include <bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int NMAX = 120000;
struct punct {
double x, y;
};
int N, nrP;
punct P[NMAX+1], st[NMAX+1];
double det(const punct& A, const punct& B, const punct& C) {
return (A.x - B.x) * (A.y - C.y) - (A.y - B.y) * (A.x - C.x);
}
bool compd(const punct& A, const punct& B) {
return det(P[1], A, B) < 0;
}
bool compx(const punct& A, const punct& B) {
if(A.x == B.x) return A.y < B.y;
return A.x < B.x;
}
void graham() {
sort(P+2, P+N+1, compd);
st[1] = P[1];
st[2] = P[2];
nrP = 2;
for(int i = 3; i <= N; i++) {
while(nrP >= 2 && det(st[nrP-1], st[nrP], P[i]) > 0)
nrP--;
st[++nrP] = P[i];
}
}
void show() {
out << nrP << '\n';
out << fixed << setprecision(6);
for(int i = nrP; i >= 1; i--)
out << st[i].x << ' ' << st[i].y << '\n';
}
int main()
{
in >> N;
int pMin = 1;
for(int i = 1; i <= N; i++) {
in >> P[i].x >> P[i].y;
if(compx(P[i], P[pMin]))
pMin = i;
}
swap(P[1], P[pMin]);
graham();
show();
return 0;
}