Pagini recente » Cod sursa (job #2825317) | Cod sursa (job #1946190) | Cod sursa (job #1424054) | Cod sursa (job #1946475) | Cod sursa (job #1546244)
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <cmath>
using namespace std;
const int nMax = 120010;
int n;
struct punct {
double x, y;
};
punct v[nMax];
vector<punct> l1, l2;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
double det(punct p, punct q, punct r) {
return (q.x - p.x)*(r.y - p.y) - (r.x - p.x)*(q.y - p.y);
}
bool vd(int d) {
return d < 0;
}
bool vs(int d) {
return d > 0;
}
void scan(bool (*vc)(int), vector<punct> &l) {
l.push_back(v[0]);
l.push_back(v[1]);
for (int i = 2; i < n; ++i) {
while ( l.size() > 1 && !vc(det( l[l.size()-1], l[l.size() - 2], v[i] )) ) {
l.erase(l.begin() + l.size() - 1);
}
l.push_back(v[i]);
}
}
bool comp(punct a, punct b) {
return vs( det( v[0], a, b ) );
}
int main() {
in >> n;
int pozMin = 0;
for (int i = 0; i < n; ++i) {
in >> v[i].x >> v[i].y;
if ((v[i].x == v[pozMin].x && v[i].y < v[pozMin].y) || v[i].x < v[pozMin].x) {
pozMin = i;
}
}
punct aux = v[0];
v[0] = v[pozMin];
v[pozMin] = aux;
sort(v + 1, v + n, comp);
//for (int i = 0; i < n; ++i) {
// cout << v[i].x << ' ' << v[i].y << '\n';
//}
//cout << "\n\n";
scan(vd, l1);
cout << l1.size() << '\n';
cout<<setprecision(6)<<fixed;
for (vector<punct>::iterator it = l1.begin(); it != l1.end(); ++it) {
cout << it -> x << ' ' << it -> y << '\n';
}
return 0;
}