Pagini recente » Cod sursa (job #1220508) | Cod sursa (job #730115) | Cod sursa (job #1473113) | Cod sursa (job #2756267) | Cod sursa (job #624046)
Cod sursa(job #624046)
#include<cstdio>
#include<cmath>
#define min(a, b) a < b ? a : b
#define max(a, b) a > b ? a : b
#define PI 3.14159265
using namespace std;
struct Point {
double x ;
double y ;
double unghiPolar_A0;
double dist_A0;
} ;
int n ;
Point L[201] ;
Point startPoint ;
Point st[201] ;
void Citire()
{
int i ;
scanf("%d", &n) ; // citesc numarul de puncte
for(i = 1; i <= n; i++)
scanf("%lf %lf", &L[i].x, &L[i].y) ; // citesc coordonatele punctelor
}
inline double Distanta(Point A, Point B)
{
return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y)) ;
}
inline double UnghiPolar(Point A, Point B)
{
Point C = {B.x, A.y} ;
double AB, AC, BC ;
double cosA, acosA ;
if(A.x == B.x && A.y == B.y) return -200 ;
if(A.x == B.x) return 90 ;
if(A.y == B.y) return 180 ;
\
AB = Distanta(A, B) ;
AC = Distanta(A, C) ;
BC = Distanta(B, C) ;
cosA = (AB * AB + AC * AC - BC * BC) / (2 * AB * AC) ;
acosA = acos(cosA) * 180.0 / PI;
if(A.y > B.y) acosA += 180 ;
else acosA = 180 - acosA ;
return acosA ;
}
inline bool UnghiIntoarcere(Point A, Point B, Point C) // verific daca unghiul de intoarcere e spre stanga
{
double S = A.x * B.y + B.x * C.y + A.y * C.x - B.y * C.x - A.x * C.y - B.x * A.y ;
return (S > 0) ;
}
Point InitializarePunctStart() // calculez punctul de start
{
int i;
Point punctStart = L[1] ;
for(i = 2; i <= n; i++)
if(L[i].x > punctStart.x) punctStart = L[i] ;
else if(L[i].x == punctStart.x && L[i].y < punctStart.y) punctStart = L[i] ;
return punctStart ;
}
void Afisare(int n)
{
int i;
for(i = 1; i <= n; i++)
printf("%.12lf \t %.12lf \t\t %.12lf \t\t %.12lf\n", L[i].x, L[i].y, L[i].unghiPolar_A0, L[i].dist_A0);
printf("\n------\n\n");
}
void SorteazaPuncteDupaUnghiPolar(Point startPoint)
{
int i, j, m ;
Point aux ;
L[0] = startPoint ;
for(i = 1; i <= n; i++)
{
L[i].unghiPolar_A0 = UnghiPolar(L[0], L[i]) ;
L[i].dist_A0 = Distanta(L[0], L[i]) ;
}
//Afisare(n);
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
if(L[i].unghiPolar_A0 < L[j].unghiPolar_A0)
{
aux = L[i];
L[i] = L[j];
L[j] = aux;
}
//Afisare(n);
Point P[201] ;
m = 2 ; P[1] = startPoint ;
for(i = 1; i <= n; i++)
if(L[i].unghiPolar_A0 >= -180 ) P[m++] = L[i];
m--;
n = 3;
L[1] = P[1];
L[2] = P[2];
for(i = 3; i <= m; i++)
if(P[i - 1].unghiPolar_A0 != P[i].unghiPolar_A0) L[n++] = P[i];
else if(P[i - 1].dist_A0 < P[i].dist_A0)
{
n--;
L[n++] = P[i];
}
n--;
//Afisare(n);
}
void Calcul()
{
int i, top = 3;
st[0] = L[1];
st[1] = L[2];
st[2] = L[3];
for(i = 4; i <= n && top >= 2; i++)
{
Point a = L[i];
Point b = st[top - 1];
Point c = st[top - 2];
if(!UnghiIntoarcere(c, b, a))
{
top--;
st[top++] = a;
}
else st[top++] = a;
}
for(i = 0; i < top; i++)
printf("%.12lf \t\t %.12lf\n", st[i].x, st[i].y);
}
int main()
{
freopen("infasuratoare.in", "r", stdin) ;
freopen("infasuratoare.out", "w", stdout) ;
Citire() ; // citire date de intrare
//printf("%d\n", UnghiIntoarcere((Point){1, 1}, (Point){2, 1}, (Point){3, 3})) ;
startPoint = InitializarePunctStart(); // punctul de start
SorteazaPuncteDupaUnghiPolar(startPoint);
Calcul();
return 0 ;
}