Pagini recente » Cod sursa (job #2314190) | Cod sursa (job #3175096) | Cod sursa (job #1382557) | Cod sursa (job #2159091) | Cod sursa (job #3139029)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
double const INF = 1e9+7;
struct Point {
double x, y;
};
Point origin;
int const NMAX = 1200000;
Point field[1 + NMAX];
bool compareAngle(Point a, Point b) {
if(a.x == origin.x && a.y == origin.y) {
return true;
}else if(b.x == origin.x && b.y == origin.y) {
return false;
}else {
if((a.y < origin.y && b.y < origin.y) || (origin.y < a.y && origin.y < b.y)) {
return ((a.y - origin.y) * (b.x - origin.x)) < ((b.y - origin.y) * (a.x - origin.x));
}else {
return (a.y < b.y);
}
}
}
double computeDeterminant(Point a, Point b, Point c) {
//cerr << a.x << ' ' << a.y << ", " << b.x << ' ' << b.y << ", " << c.x << ' ' << c.y << ": " << ((a.x * b.y) + (b.x * c.y) + (c.x * a.y)) - ((b.x * a.y) + (c.x * b.y) + (a.x * c.y)) << '\n';
return ((a.x * b.y) + (b.x * c.y) + (c.x * a.y)) - ((b.x * a.y) + (c.x * b.y) + (a.x * c.y));
}
int main() {
int n;
in >> n;
origin.x = INF;
origin.y = INF;
for(int i = 1;i <= n;i++) {
in >> field[i].x >> field[i].y;
if(field[i].x < origin.x) {
origin.x = field[i].x;
origin.y = field[i].y;
}else if(field[i].x == origin.x){
origin.y = min(field[i].y, origin.y);
}
}
sort(field+1, field+n+1, compareAngle);
vector <Point> st;
//cerr << origin.x << ' ' << origin.y << '\n';
for(int i = 1;i <= n;i++) {
while(st.size() > 1 && (computeDeterminant(st[st.size() - 2], st[st.size() - 1], field[i]) < 0.0)) {
st.pop_back();
}
st.push_back(field[i]);
}
out << st.size() << '\n';
for(int i = 0;i < st.size();i++) {
out << st[i].x << ' ' << st[i].y << '\n';
}
return 0;
}