Pagini recente » Cod sursa (job #1606634) | Cod sursa (job #1448405) | Cod sursa (job #1226822) | Cod sursa (job #1530369) | Cod sursa (job #2121560)
#include <iostream>
#include <algorithm>
#include <fstream>
#include <limits>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in" );
ofstream g("infasuratoare.out");
int N, refPoint;
int infas[100003];
float slope[100003];
struct PT {
float x;
float y;
float slope;
}point[100003];
bool cmp(PT A, PT B) { return A.slope < B.slope; }
/// Functia determinant folosita sa comparam doua unghiuri
/// Returneaza pozitiv daca C se afla in stanga dreptei AB
float Determinant(PT A, PT B, PT C) {
return (A.x*B.y + B.x*C.y + C.x*A.y) - (B.y*C.x + A.y*B.x + A.x*C.y);
}
/// Functia ComputeSlope returneaza panta facuta de dreapta AB
float ComputeSlope(PT A, PT B)
{
float diffY = B.y - A.y;
float diffX = B.x - A.x;
if ( diffX == 0 )
{
if ( diffY > 0 ) return numeric_limits<float>::max();
if ( diffY < 0 ) return numeric_limits<float>::min();
return 0;
}
return diffY / diffX;
}
/// Rezolvare convex hull
void ComputeConvex()
{
int refPoint = 1;
for ( int i=1; i<=N; i++ )
if ( point[i].x < point[refPoint].x ||
(point[i].x == point[refPoint].x && point[i].y < point[refPoint].y) )
refPoint = i;
swap(point[refPoint], point[1]); refPoint = 1;
/// Cautare cel mai din stanga si de jos punct pe care il vom folosi ca referinta
/// Acest punct se afla sigur pe infasuratoare
for ( int i=2; i<=N; i++ )
point[i].slope = ComputeSlope(point[refPoint], point[i]);
/// Calculam panta de la punctul de referinta pana la fiecare dintre celelalte
sort(point+2, point+N+1, cmp);
/// Sortam pantele calculate pentru a le parcurge in ordinea in care pot aparea in infasuratoare
for ( int i=1; i<=N; i++ )
cout << point[i].x << ' ' << point[i].y << ' ' << point[i].slope << '\n';
infas[++infas[0]] = refPoint;
point[N+1] = point[refPoint];
for ( int i=2; i<=N+1; i++ )
{
while ( infas[0] > 1 && Determinant(point[infas[infas[0]-1]], point[i], point[infas[infas[0]]]) > 0 )
--infas[0];
infas[++infas[0]] = i;
}
/// Parcurgem toate punctele in ordinea unghiului pe care il fac cu punctului de referinta
}
int main()
{
f >> N;
for ( int i=1; i<=N; i++ )
f >> point[i].x >> point[i].y;
ComputeConvex();
g << infas[0] - 1 << '\n';
g << fixed << setprecision(6);
for ( int i=1; i<infas[0]; i++ )
g << point[infas[i]].x << ' ' << point[infas[i]].y << '\n';
}