Pagini recente » Rating Indi Botoc (indibotoc) | Cod sursa (job #1256204) | Cod sursa (job #230938) | Cod sursa (job #644631) | Cod sursa (job #1168804)
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
const int N = 120000;
const bool supportLine = false, medianLine = true;
struct Point{
double x, y;
Point() : x(0), y(0) {};
Point(double x, double y) : x(x), y(y) {};
inline Point operator-(const Point P) const {
return Point(x - P.x, y - P.y);
}
inline double operator*(const Point P) const {
return x * P.y - y * P.x;
}
inline bool operator<(const Point& P) const {
return x < P.x || (x == P.x && y < P.y);
}
};
Point P[N], hull[N];
int nrP;
ofstream out("rubarba.out");
inline long long crossProduct(Point A, Point B, Point C){
return (B - A) * (C - A);
}
int getConvexHull(Point P[], int nrP){
sort(P, P + nrP);
int hullSize = 0;
for (int i = 0 ; i < nrP ; i++){
while ( hullSize > 1 && crossProduct(hull[hullSize - 2], hull[hullSize - 1], P[i]) <= 0 )
hullSize--;
hull[ hullSize++ ] = P[i];
}
int capSize = hullSize;
for (int i = nrP - 2 ; i >= 0 ; i--){
while ( hullSize > capSize && crossProduct(hull[hullSize - 2], hull[hullSize - 1], P[i]) <= 0 )
hullSize--;
hull[ hullSize++ ] = P[i];
}
hullSize--;
for (int i = 0 ; i < hullSize ; i++)
P[i] = hull[i];
return hullSize;
}
int main(){
ifstream in("infasuratoare.in");
in >> nrP;
for (int i = 0 ; i < nrP ; i++)
in >> P[i].x >> P[i].y;
in.close();
nrP = getConvexHull(P, nrP);
ofstream out("infasuratoare.out");
out << nrP << '\n';
out << setprecision(6) << fixed;
for (int i = 0 ; i < nrP ; i++)
out << P[i].x << ' ' << P[i].y << '\n';
out.close();
return 0;
}