Pagini recente » Cod sursa (job #2546163) | Istoria paginii runda/baraj2017/clasament | Cod sursa (job #334727) | Cod sursa (job #1936089) | Cod sursa (job #1540014)
/*
Infasuratoare convexa:
Implementare algoritm:
https://drive.google.com/file/d/0Bxh__ul1ji8IZVhqSTVYZk9Pc190MlRfUXc1aERKSC1teXc0/view?usp=sharing
Exceptie: ordonarea se face dupa abscisa si ordonata; nu invers
*/
#include <iostream>
#include <fstream>
#include <algorithm> // sort
#include <cmath> // acos, sqrt
#include <vector>
#include <iomanip>
using namespace std;
struct punct {double x, y, ang_pol;};
vector<punct> puncte;
vector<punct> stiva; // va contine punctele poligonului in ordine invers-trigonometrica
punct min_punct;
unsigned long min_p = 0, n;
double dist_ipot, dist_cat, dist1, dist2;
double E(punct p1, punct p2, punct p)
{
return p1.x*p2.y + p2.x*p.y + p.x*p1.y - p1.x*p.y - p2.x*p1.y - p.x*p2.y;
}
bool sort_puncte(punct p1, punct p2)
{
if(p1.ang_pol < p2.ang_pol) return 1; // se muta p2 in locul lui p1 daca unghiul polar al lui p2 este mai mic
if(p1.ang_pol == p2.ang_pol)
{
dist1 = (p1.x-puncte[min_p].x)*(p1.x-puncte[min_p].x)+(p1.y-puncte[min_p].y)*(p1.y-puncte[min_p].y);
dist2 = (p2.x-puncte[min_p].x)*(p2.x-puncte[min_p].x)+(p2.y-puncte[min_p].y)*(p2.y-puncte[min_p].y);
if(dist1 < dist2) return 1; // la unghiuri egale se muta doar daca dist AP2 > dist AP1
else if(dist1 == dist2)
{
if(p1.y > p2.y) return 1; // la distante egale se ordoneaza dupa y desc. (???)
}
}
return 0;
}
int main()
{
ifstream fin("infasuratoare.in");
fin >> n;
for(unsigned long i = 0; i < n; ++i)
{
fin >> min_punct.x >> min_punct.y;
min_punct.ang_pol = -1;
puncte.push_back(min_punct); // adaug punctul citit in vector
if(puncte[i].x < puncte[min_p].x) min_p = i;
else if(puncte[i].x == puncte[min_p].x && puncte[i].y < puncte[min_p].y) min_p = i;
}
fin.close();
min_punct.x = puncte[min_p].x;
min_punct.y = puncte[min_p].y;
puncte.erase(puncte.begin() + min_p); // mut punctul cu coordonata x minima (si y ?) pe pozitia 0 in vector
puncte.insert(puncte.begin(), min_punct);
for(unsigned long i = 1; i < puncte.size(); ++i)
{
/*
M2(i.x, i.y)
x
/|
/ |
/ |
dist_ipot => / |
/ |
/ |
/ |
/ang |
x--------x
M1(min.x, min.y) ^ M3(min.x, i.y)
|
|
|
dist_cat
*/
dist_ipot = sqrt((puncte[i].x-min_punct.x)*(puncte[i].x-min_punct.x)+(puncte[i].y-min_punct.y)*(puncte[i].y-min_punct.y)); // M1M2
dist_cat = min_punct.y-puncte[i].y; // M1M3
if(dist_cat < 0) dist_cat = -dist_cat; // distanta nu poate fi negativa
if(puncte[i].y < min_punct.y) dist_cat = -dist_cat; // daca punctul M2 se afla sub M1, atunci cos trebuie sa fie negativ (IMPORTANT!) (???)
puncte[i].ang_pol = acos(dist_cat/dist_ipot); // unghiul polar aflat prin arccos(cos(ang))
}
sort(puncte.begin()+1, puncte.end(), sort_puncte); // sortez punctele CU EXCEPTIA celui de pe pozitia 0
for(unsigned long i = puncte.size()-1; i > 1; --i) // se sterg punctele care au acelasi unghi polar, ramanand doar cel mai distantat de M1
{
if(puncte[i].ang_pol == puncte[i-1].ang_pol)
{
dist1 = (puncte[i].x-puncte[min_p].x)*(puncte[i].x-puncte[min_p].x)+(puncte[i].y-puncte[min_p].y)*(puncte[i].y-puncte[min_p].y);
dist2 = (puncte[i-1].x-puncte[min_p].x)*(puncte[i-1].x-puncte[min_p].x)+(puncte[i-1].y-puncte[min_p].y)*(puncte[i-1].y-puncte[min_p].y);
if(dist1 != dist2) puncte.erase(puncte.begin() + i); // in cazul in care punctele au distanta egala si unghiul egal, atunci nu se mai sterg (???)
}
}
stiva.push_back(puncte[0]); // se adauga primele 3 puncte in stiva
stiva.push_back(puncte[1]);
stiva.push_back(puncte[2]);
for(unsigned long i = 3; i < puncte.size(); ++i) // se adauga urmatoarele puncte
{
stiva.push_back(puncte[i]); // adaugare
while(E(stiva[stiva.size()-1-2], stiva[stiva.size()-1-1], stiva[stiva.size()-1]) > 0) // se verifica daca ultimul punct adaugat ANULEAZA CONVEXITATEA (se afla in stanga vectorului determinat de antepenultimul si penultimul punct (cu varful in penultimul))
{// de ce stanga anuleaza convexitatea? pt. ca punctele sunt ordonate in vector crescator dupa unghiul polar care CRESTE cu cat punctul se afla mai sus decat punctul M1, asadar
stiva.erase(stiva.end()-1-1); // se sterge penultimul punct din vector pana cand SE PASTREAZA CONVEXITATEA cu ultimul punct
}
}
ofstream fout("infasuratoare.out");
fout << stiva.size() << endl;
for (unsigned i = stiva.size(); i-- > 0; )
{
fout << fixed << setprecision(6) << stiva[i].x << ' ' << stiva[i].y << endl;
}
fout.close();
return 0;
}