Najpierw krytyka kodu, żebyś się czegoś nauczył.
Czemu się rozjeżdza?
for (int i = 0; i < ile; i++)
{
if (Punkty[i].first == x && Punkty[i].second == y)
{
cout << "o ";
}
}
cout << ". ";
niezależnie od tego czy w danej linii zaznaczyłeś punkt i tak potem stawiasz kropke. Można to załatwić flagą czyNarysowanoPunkt, ale trzeba pamiętać o wyeliminowaniu rysowania kilku o przez kilka punktów w tym samym miejscu.
Co do samego rozjeżdzania to można użyć z nagłowka <iomanip>
cout << setw(3) << y << ":";
wtedy szerokość wypisana będzie stała.
sort(Punkty.begin(), Punkty.end());
Nie wiem czy wiesz co domyślnie robi sort dla pary - porównuje firsty, jesli równe to second. Możliwe, że to chciałes osiągnąć, bo ja np nie ograniam po co tu coś sortować.
for (int i = ile - 1; i >= 0; i--)
{
Tymczasowy.push_back(make_pair(Punkty[i].first, Punkty[i].second));
}
Punkty.clear();
for (int i = 0; i < ile; i++)
{
Punkty.push_back(make_pair(Tymczasowy[i].first, Tymczasowy[i].second));
cout << "Punkt " << i + 1 << ": ";
cout << Punkty[i].first << " " << Punkty[i].second << endl;
}
Odwracasz posortowany vector i przepisujesz spowrotem do oryginalnego. Ale wiesz, że jest coś takiego jak std::reverse(Punkty.begin(), Punkty.end())? I jest też coś takiego jak konstruktor kopiujący wektora, nie musisz tego robić ręcznie, jeśli nie chcemy tworzyć nowego vectora to można też wypełnić go jedną metodą:
Punkty.insert(Punkty.end(), Tymczasowy.begin(), Tymczasowy.end());
void Pseudograf(vector<pair<int, int> >& Punkty, int ile)
vector ma metode size :P, nie musisz przesyłać długości.
Co do rozwiąznia problemu - co za dziwnie postawiony problem :P. Kminiłem sporo nad tym aż wymyśliłem. Trzeba zrobić dokładnie to co jest napisane w poleceniu xD. Czyli dopóki jest jeszcze jakiś punkt w zbiorze to szukasz punktów bezwględnie maksymalnych, czyli takich nad którymi żaden inny punkt nie dominuje. Gdy znajdziesz te punkty to masz jedną warstwę. Wywalasz je więc ze zbioru punktów i powtarzasz rozumowanie. Oczywiście napisałem to, żeby sprawdzić czy działa. Dodałem komentarze, have fun:
struct Punkt {
int x, y;
//przeciazenie operatora, dla wlasnej wygody
//implementuje definicje dominacji z zadania
bool operator>(const Punkt& p2) const {
return x > p2.x && y > p2.y;
}
//funkcja std::remove, ktorej bedziemy uzywac wymaga
//zeby obiekty dalo sie do siebie przyrownac
bool operator==(const Punkt& p2) const {
return x == p2.x && y == p2.y;
}
};
//zeby dalo sie wypisywac bezposrednio cout<<punkt;
std::ostream& operator<<(std::ostream& out, const Punkt& p) {
return out << "[" << p.x << "," << p.y << "]";
}
int main() {
vector<Punkt> Punkty = {
{ 1,1 },{ 1,1 },{ 1,2 },{ 5,3 },{ 3,5 },{ 10,10 },{ 2,6 } };
//tworze zbior roboczy - kopie punktow, bo bedziemy potrzebowali usuwac punkty
vector<Punkt> ZbiorRoboczy(Punkty);
//flaga, ktora mowi czy dany punkt jest maksymalny w obecnym zbiorze
bool maksymalny = true;
//warstwy rozumiane w ten sposob, ze Warstwy[i] to wektor punktow
//nalezacych do i-tej warstwy
vector<vector<Punkt>> Warstwy;
//sprawdzamy czy zbior roboczy nie jest juz pusty
//w tej petli bedziemy tworzyc kolejne warstwy
for (int warstwa = 0; ZbiorRoboczy.size() > 0; warstwa++)
{
//iniciujemy warstwe pustym wektorem punktow
Warstwy.push_back(vector<Punkt>());
//dla kazdego punktu sprawdzamy czy dominuje on nad wszystkimi innymi
//dla kazdego punktu porownujemy go z cala reszta
//jesli ktorykolwiek bedzie nad nim dominowal to przerywamy
for (int i = 0; i < ZbiorRoboczy.size(); i++) {
maksymalny = true;
for (int j = 0; j < ZbiorRoboczy.size(); j++) {
if (i != j && ZbiorRoboczy[j] > ZbiorRoboczy[i]) {
maksymalny = false;
break;
}
}
if (maksymalny)
Warstwy[warstwa].push_back(ZbiorRoboczy[i]);
}
//usuwamy punkty dodane do warstwy ze zbioru roboczego (tresc zadania)
for (auto p : Warstwy[warstwa]) {
//skopiowane z stackoverflow "how to remove element by value from vector"
ZbiorRoboczy.erase(std::remove(ZbiorRoboczy.begin(), ZbiorRoboczy.end(), p), ZbiorRoboczy.end());
}
}
//wypisujemy warstwy
for (auto& warstwa : Warstwy) {
for (auto& punkt : warstwa) {
cout << punkt << " ";
}
cout << endl;
}
}
Pasowałby to porozdzielać na funkcje, ale jest późno i już mi się nie chce :P
Wydaje mi się, że to działa. Jak czegoś nie rozumiesz to pytaj. Przeciążanie operatorów dla swojej własnej wygody i jeden do funkcji std::remove, ale z pewnością da się wywalić element z vectora bez użycia przeciążania operatorów, jeśli tego nie ogarniasz.
