Cod sursa(job #1256359)

Utilizator Simona13Simona Mihalca Simona13 Data 6 noiembrie 2014 09:42:14
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include <iostream>
#include<fstream>
#include <algorithm>
#include <vector>
using namespace std;

typedef double coord_t;         // coordinate type
typedef double coord2_t;  // must be big enough to hold 2*max(|coordinate|)^2

struct Point {
	coord_t x, y;

	bool operator <(const Point &p) const {
		return x < p.x || (x == p.x && y < p.y);
	}
};

// 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.
coord2_t cross(const Point &O, const Point &A, const Point &B)
{
	return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

// 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.
vector<Point> 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(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(H[k-2], H[k-1], P[i]) <= 0)
            k--;
		H[k++] = P[i];
	}

	H.resize(k);
	return H;
}

int main()
{   vector<Point> P,P1;
    Point a;
    ifstream f("infasuratoare.in");
    int n;
    f>>n;
    for (int i=0;i<n;i++)
        {f>>a.x;
        f>>a.y;
        P.push_back(a);
        }
    P1=convex_hull(P);
    ofstream g("infasuratoare.out");
    g<<P1.size()-1<<endl;
    for( int i=1; i< P1.size();i++)
        g<<P1[i].x<<" "<<P1[i].y<<endl;
    f.close();
    g.close();
    return 0;
}