Pagini recente » Cod sursa (job #1151959) | Cod sursa (job #815376) | Cod sursa (job #2762108) | Cod sursa (job #2954509) | Cod sursa (job #1336910)
#include<fstream>
#include<vector>
#include<algorithm>
#include<limits>
#include<iomanip>
using namespace std;
typedef double var;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const var INF = numeric_limits<var>::max();
struct Point {
var x, y;
Point(var a, var b) {
x = a;
y = b;
}
Point() {}
};
Point l;
var angle(Point &p, Point &q) {
var &x1 = p.x, &y1 = p.y;
var &x2 = q.x, &y2 = q.y;
if(x1 == x2) {
if(y1 < y2) return INF;
else return -INF;
} else {
return (y2 - y1) / (x2 - x1);
}
}
bool cmp(Point p, Point q) {
return angle(l, p) < angle(l, q);
}
var crossprod(Point &p, Point &q, Point &r) {
var &x1 = p.x, &y1 = p.y;
var &x2 = q.x, &y2 = q.y;
var &x3 = r.x, &y3 = r.y;
// | i , j , k|
// |x2-x1, y2-y1, 0|
// |x3-x1, y3-y1, 0|
return (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1);
}
int main() {
int n;
var x, y;
vector<Point> POINTS;
l = Point(INF, 0);
fin>>n;
POINTS.resize(n);
for(int i=0; i<n; i++) {
fin>>x>>y;
POINTS[i] = Point(x, y);
if(l.x > x)
l = POINTS[i];
}
sort(POINTS.begin(), POINTS.end(), cmp);
vector<Point> SOL;
SOL.push_back(l);
for(int i=1; i<n; i++) {
while(SOL.size() > 1 && crossprod( *(SOL.end() - 2), *(SOL.end() - 1), POINTS[i]) < 0)
SOL.pop_back();
SOL.push_back(POINTS[i]);
}
fout << SOL.size() << '\n';
for(vector<Point>::iterator it = SOL.begin(); it != SOL.end(); ++it) {
fout << setprecision(20) << fixed << (*it).x << " " << (*it).y << '\n';
}
}