Pagini recente » Cod sursa (job #2951408) | Cod sursa (job #14350) | Cod sursa (job #2833266) | Cod sursa (job #2778681) | Cod sursa (job #1422659)
#include <algorithm>
#include <vector>
#include <iomanip>
#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Point {
double x, y;
bool operator <(const Point &p) const {
return x < p.x || (x == p.x && y < p.y);
}
Point(){x=y=0;}
Point(double a, double b){
x = a;
y = b;
}
};
// 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product.
// Returns a positive value, if OAB makes a counter-clockwise turn,
// negative for clockwise turn, and zero if the points are collinear.
double cross(const Point &O, const Point &A, const Point &B)
{
return (long)(A.x - O.x) * (B.y - O.y) - (long)(A.y - O.y) * (B.x - O.x);
}
double cross_product(const Point &a, const Point &b, const Point &c){
return (b.x*c.y)+(a.x*b.y)+(c.x*a.y)-(b.x*a.y)-(b.y*c.x)-(a.x*c.y);
}
// Returns a list of points on the convex hull in counter-clockwise order.
// Note: the last point in the returned list is the same as the first one.
void convex_hull(vector<Point> P)
{
int n = P.size(), k = 0;
vector<Point> H(2*n);
// Sort points lexicographically
sort(P.begin(), P.end());
// Build lower hull
for (int i = 0; i < n; ++i) {
while (k >= 2 && cross_product(H[k-2], H[k-1], P[i]) <= 0) k--;
H[k++] = P[i];
}
// Build upper hull
for (int i = n-2, t = k+1; i >= 0; i--) {
while (k >= t && cross_product(H[k-2], H[k-1], P[i]) <= 0) k--;
H[k++] = P[i];
}
H.resize(k);
fout<<setprecision(6)<<fixed;
fout << H.size()-1 << endl;
for(int i =0; i < H.size()-1; i++){
fout << H[i].x << " " << H[i].y << endl;
}
}
int main(){
vector<Point>v;
int n;
fin >> n;
for(int i =0 ; i < n; i++){
double a,b;
fin >> a >> b;
v.push_back(Point(a,b));
}
convex_hull(v);
return 0;
}