Pagini recente » Cod sursa (job #3364359) | Cod sursa (job #3364002) | Atasamentele paginii Profil DianaOfelia | Cod sursa (job #3364015) | Cod sursa (job #3364112)
#include <bits/stdc++.h>
# define x first
# define y second
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
pair<double,double> P[120005];
vector<pair<double, double>> sus, jos, sol1, sol2;
pair<double, double> A, B;
int N;
double detArie(pair<double, double> M, pair<double, double> N, pair<double, double> O)
{
return (N.x - M.x) * (O.y - M.y) - (N.y - M.y) * (O.x - M.x);
}
void detJumatati()
{
/// separ punctele in fct de pozitia lor fata de dreapta AB (sus sau jos)
/// folosim formula ariei:
/// S = 1/2 * (( Xa * Yp - Xp * Ya) + (Xp * Yb - Xb * Yp) + ( Xb * Ya - Xa * Yb)) =
/// = 1/2 * ( Xa * (Yp - Yb) + Xb * (Ya - Yp) + Xp * (Yb - Ya))
/// printr-un artificiu de calcul (sau cu determinanti) obtinem:
/// 2S = (Xp - Xa) * (Yb - Ya) - (Yp - Ya) * (Xb - Xa)
/// in fct de semnul acestei arii, pot vedea pe ce parte a dr AB este pct P
/// S > 0 => P este jos
/// S < 0 => P este sus
for(int i = 1; i < N - 1; i++)
{
/// arie = 2S
double arie = detArie(A, P[i], B);
if(arie > 0)
{
jos.push_back(P[i]);
}
else
{
sus.push_back(P[i]);
}
}
sus.push_back(B);
jos.push_back(B);
}
void infasuratoare(vector<pair<double, double>> points, bool caz)
{
if(points.empty() == 1)
{
return;
}
stack<pair<double,double>> inf;
inf.push(A);
pair<double,double> C;
C = points[0];
for(int i = 1; i < points.size(); i++)
{
double arie = detArie(inf.top(), C, points[i]);
/// daca arie > 0 (pt infasuratoarea de sus) => am mers trigonometric => unghiul > 180 => pct C trebuie eliminat
/// pt infasuratoarea de jos se schimba semnul
while(inf.empty() == 0 && (caz == 0 && arie > 0) || (caz == 1 && arie < 0))
{
/// top points
/// /\ /
/// / \/
/// / C
C = inf.top();
inf.pop();
if(inf.empty() == 0)
{
arie = detArie(inf.top(), C, points[i]);
}
}
inf.push(C);
C = points[i];
}
inf.push(B);
while(inf.empty()==0)
{
if(caz == 0)
sol1.push_back({inf.top().x, inf.top().y});
else
sol2.push_back({inf.top().x, inf.top().y});
inf.pop();
}
}
/*void afisare()
{
for(int i = 0; i < sol1.size(); i++)
{
cout<<setprecision(12)<< fixed<< sol1[i].x<<' '<<sol1[i].y<<'\n';
}
reverse(sol2.begin(), sol2.end());
for(int i = 1; i + 1 < sol2.size(); i++)
{
fout<<setprecision(12)<< fixed<< sol2[i].x<<' '<<sol2[i].y<<'\n';
}
}*/
int main()
{
fin>>N;
for(int i = 0; i < N; i++)
{
fin>>P[i].x>>P[i].y;
}
sort(P, P + N);
A = P[0];
B = P[N - 1];
detJumatati();
infasuratoare(sus, 0);
infasuratoare(jos, 1);
for(int i = 0; i < sol1.size(); i++)
{
fout<<setprecision(12)<< fixed<< sol1[i].x<<' '<<sol1[i].y<<'\n';
}
reverse(sol2.begin(), sol2.end());
for(int i = 1; i + 1 < sol2.size(); i++)
{
fout<<setprecision(12)<< fixed<< sol2[i].x<<' '<<sol2[i].y<<'\n';
}
// afisare();
return 0;
}