Pagini recente » Cod sursa (job #2318862) | Cod sursa (job #2556213) | Cod sursa (job #2342090) | Cod sursa (job #885962) | Cod sursa (job #547240)
Cod sursa(job #547240)
#include <fstream>
#include <iostream>
#include <cmath>
using namespace std;
#define DIM 130000
#define eps 0.001
struct Punct{
double x, y;
} a[DIM], aux;
int st[DIM];
int n, nrvf; //nr total de Puncte, nr de vf ale invelitorii convexe
double minx = 1e+10, miny = 1e+10;
void Citeste();
void Sort();
double Unghi(int);
double Raza(int);
int Conditie(int,int);
void Graham();
int IntoarcereDreapta(int);
void Afis();
int main()
{
Citeste();
Sort();
Graham();
Afis();
return 0;
}
void Citeste()
{
ifstream fin("conv.in");
fin >> n;
int i, pmin;
for (i = 1; i <= n; i++)
{
fin >> a[i].x >> a[i].y;
if ( fabs(a[i].y - miny) < eps && a[i].x < minx) // la aceeasi ordonata conteaza abscisa
{
minx = a[i].x;
pmin = i;
}
else if (a[i].y < miny)
{
minx = a[i].x;
miny = a[i].y;
pmin = i;
}
}
aux = a[pmin]; //plasam primul element din invelitoare in pozitia 1
a[pmin] = a[1];
a[1] = aux; // elem de ordonata minima
fin.close();
}
// Never
void Sort() // sortare dupa unghiul polar si la acelasi unghi, dupa raza polara
{
int i, j;
for(i = 2; i < n; i++)
for(j = i + 1; j <= n; j++)
{
if (Conditie(i, j))
{
aux = a[i];
a[i] = a[j];
a[j] = aux;
}
}
}
int Conditie(int i, int j)
{
if ( fabs(Unghi(i) - Unghi(j)) < eps && Raza(i) > Raza(j)) //daca unghiurile sunt egale ordonam dupa raza
return 1;
if (Unghi(i) > Unghi(j))
return 1;
return 0;
}
double Unghi(int i)
{
double yi, xi;
yi = a[i].y - miny;
xi = a[i].x - minx;
if (fabs(xi) < eps) // a[i].x == minx => Punctele sunt pe aceeasi verticala
return 90;
if (xi > 0)
return (180 * (atan(yi/xi) / M_PI));
return (180 - fabs(180 * (atan(yi/xi) / M_PI)));
}
double Raza(int i)
{
double yi, xi;
yi = a[i].y - miny;
xi = a[i].x - minx;
return sqrt(xi*xi + yi*yi); // era ma bine fara radical (compari razele la patrat)
}
void Graham()
{
int i;
st[0] = 1; //primele trei Puncte se introduc in stiva
st[1] = 2;
st[2] = 3;
nrvf = 2;
for (i = 4; i <= n; i++) //introducem, in ordine, toate cele n-3 Puncte ramase
{
while (IntoarcereDreapta(i))
st[nrvf--] = 0; // scoatem din stiva toate punctele fata de care varful i "se intoarce la dreapta"
st[++nrvf] = i;
}
}
int IntoarcereDreapta(int i) //calculam cu ajutorul produsului vectorial semnul sinusului
{
double x1, y1, x2, y2;
x1 = a[st[nrvf]].x - a[st[nrvf-1]].x;
y1 = a[st[nrvf]].y - a[st[nrvf-1]].y;
x2 = a[i].x-a[st[nrvf-1]].x;
y2 = a[i].y-a[st[nrvf-1]].y;
if(x1 * y2 - x2 * y1 <= 0) // nici coliniaritate nu se accepta (<= nu <)
return 1;
return 0;
}
void Afis()
{
ofstream fout("conv.out");
int i;
for (i = 0; i <= nrvf; i++)
fout << a[st[i]].x << " " << a[st[i]].y << '\n';
/*
for (i = 1; i <= n; i++)
fout << a[i].x << " " << a[i].y << '\n';
*/
fout.close();
}