Pagini recente » Cod sursa (job #1945029) | Cod sursa (job #1593210) | Cod sursa (job #234180) | Borderou de evaluare (job #2089413) | Cod sursa (job #1988740)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int nmax = 120000;
struct Point {
double x;
double y;
bool operator<(Point other) const {
if(x != other.x)
return x < other.x;
else
return y < other.y;
}
};
Point v[1 + nmax];
int sol[1 + nmax], nsol;
double det3(Point a, Point b, Point c) {
double plus = a.x * b.y + a.y * c.x + b.x * c.y;
double minus = b.y * c.x + b.x * a.y + a.x * c.y;
return (plus - minus);
}
bool cmp(Point a, Point b) {
return ( det3(v[0], a, b) > 0 );
}
int main() {
int n;
in >> n;
for(int i = 0; i < n; ++ i) {
in >> v[i].x >> v[i].y;
if( v[i] < v[0] ) {
swap(v[0], v[i]);
}
}
sort(v + 1, v + n, cmp);
nsol = 2;
sol[1] = 0;
sol[2] = 1;
int i = 2;
while(i < n) {
if(det3(v[sol[nsol - 1]], v[sol[nsol]], v[i]) > 0) {
sol[++nsol] = i;
++ i;
} else {
-- nsol;
}
}
out << nsol << '\n';
out << setprecision(6) << fixed;
for(int i = 1; i <= nsol; ++ i) {
out << v[sol[i]].x << " " << v[sol[i]].y << '\n';
}
return 0;
}