Pagini recente » Cod sursa (job #1838725) | Profil cristina-alina | Cod sursa (job #1559820) | Cod sursa (job #2541398) | Cod sursa (job #2756504)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;
ifstream fin ("infasuratoare.in") ;
ofstream fout ("infasuratoare.out") ;
struct POINT
{
double x, y ;
};
const int NMAX = 120000 ;
const double eps = 1.0e-14 ;
POINT P[NMAX + 5], LL ;
int h[NMAX + 5] ;
double cp(const POINT &P1, const POINT &P2, const POINT &P3)
{
return(P2.x - P1.x) * (P3.y - P2.y) - (P2.y - P1.y) * (P3.x - P2.x) ;
}
int ccw(const POINT &P1, const POINT &P2, const POINT &P3)
{
double crossp = cp(P1, P2, P3) ;
if(fabs(crossp) < eps)
return 0 ;
if(crossp > -eps)
return 1 ;
return -1 ;
}
bool cmp (POINT &P1, POINT &P2)
{
return ccw(LL, P1, P2) > 0 ;
}
double aria_poligon (int n)
{
double aria ;
int i ;
P[n] = P[0] ;
aria = 0 ;
for(int i = 0 ; i <= n ; i++)
aria = P[i].x * P[i + 1].y - P[i + 1].x * P[i].y ;
aria = 0.5 * fabs(aria) ;
return aria ;
}
int main()
{
int n, i, top ;
double a, b ;
fin >> n >> a >> b ;
P[0].x = a ;
P[0].y = b ;
for(i = 1 ; i < n ; i++)
{
fin >> a >> b ;
P[i].x = a ;
P[i].y = b ;
if(P[i].y - P[0].y <= -eps or (fabs(P[i].y - P[0].y) < eps) and P[i].x - P[0].x <= -eps)
swap(P[i], P[0]) ;
}
LL = P[0] ;
P[n] = P[0] ;
h[0] = 0 ;
h[1] = 1 ;
sort(P + 1, P + n, cmp) ;
top = 1 ;
i = 2 ;
while(i <= n)
if(ccw(P[h[top - 1]], P[h[top]], P[i]) > 0)
{
h[++top] = i ;
i++;
}
else top--;
fout << top << '\n' ;
for(i = 0 ; i < top ; i++)
fout << fixed << setprecision(6) << P[h[i]].x << ' ' << setprecision(6) << P[h[i]].y << '\n' ;
return 0;
}