Pagini recente » Cod sursa (job #2251219) | Cod sursa (job #2305492) | Cod sursa (job #2102262) | Cod sursa (job #1680910) | Cod sursa (job #1810155)
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
const int N = 120100;
int i, n, s[N], k;
bool viz[N];
struct el {
double x,y;
} v[N];
long double cm(el A, el B) {
if (A.x != B.x) {
return A.x>B.x;
}
return A.y<B.y;
}
inline long double det(int i, int j, int k) {
return 1.0*v[i].x*v[j].y+v[j].x*v[k].y+v[i].y*v[k].x-v[i].y*v[j].x-v[j].y*v[k].x-v[i].x*v[k].y;
}
int main() {
fin >> n;
for (i = 1; i <= n; ++i) {
fin >> v[i].x >> v[i].y;
}
sort(v + 1, v + n + 1, cm);
viz[2] = 1;
s[1] = 1;
s[2] = 2;
k = 2;
for (i = 3; i <= n; ++i) {
if (det(s[k - 1], s[k], i) < 0) {
s[++k] = i;
viz[i] = 1;
} else {
while (det(s[k - 1], s[k], i) >= 0 && k > 1){
viz[s[k]] = 0;
s[k] = 0;
k--;
}
s[++k] = i;
viz[i] = 1;
}
}
for (i = n - 1; i >= 1; --i) {
if (!viz[i]) {
if (det(s[k - 1], s[k], i) < 0) {
s[++k] = i;
viz[i] = 1;
} else {
while (det(s[k - 1], s[k], i) >= 0 && k > 1) {
viz[s[k]] = 0;
s[k] = 0;
k--;
}
s[++k] = i;
viz[i] = 1;
}
}
}
fout << k - 1 << "\n";
k--;
for (i = k - 1; i > 0; --i)
fout << fixed << setprecision(6) << v[s[i]].x << " " << v[s[i]].y <<"\n";
fout << v[s[k]].x << " " << v[s[k]].y << "\n";
return 0;
}