Pagini recente » Cod sursa (job #2307609) | Monitorul de evaluare | Cod sursa (job #2302340) | Cod sursa (job #2487544) | Cod sursa (job #3303901)
#include <fstream>
//#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
//ifstream cin("pachete.in");
//ofstream cout("pachete.out");
struct Poziti {
int x;
int y;
};
int PozitieXDeIncepere, PozitieYDeIncepere;
bool EstePosibil(vector<Poziti>NordEst, vector<Poziti>SudEst, vector<Poziti>NordVest, vector<Poziti>SudVest,bitset<50000>NordEstBool, bitset<50000>SudEstBool, bitset<50000>NordVestBool, bitset<50000>SudVestBool, int NrDeDrumuri) {
int drumuri = 0, NE = NordEst.size()-1, SE = SudEst.size()-1, NV = NordVest.size()-1, SV = SudVest.size()-1;
bool pereche = false;
while (NE >= 0 && drumuri <= NrDeDrumuri) {
int x = NordEst[NE].x;
for (int i = NE - 1; i >= 0; i--) {
if (NordEstBool[i] == false) {
}else if (NordEst[i].x <= x) {
NordEstBool[i] = false;
x = NordEst[i].x;
i--;
pereche = true;
}
}
if (pereche == false) {
if (NordEst[NE].x == PozitieXDeIncepere && NordEst[NE].y > PozitieYDeIncepere) {
drumuri--;
NordVest.push_back(NordEst[NE]);
}
if (NordEst[NE].x > PozitieXDeIncepere && NordEst[NE].y == PozitieYDeIncepere) {
drumuri--;
SudEst.push_back(NordEst[NE]);
}
}
pereche = false;
NE--;
while (NE >= 0 && NordEstBool[NE] == false ) {
NE--;
}
drumuri++;
}
while (SE >= 0 && drumuri <= NrDeDrumuri) {
int y = SudEst[SE].y;
for (int i = SE-1; i >= 0; i--) {
if (SudEstBool[i] == false) {
}else if (SudEst[i].y <= y) {
SudEstBool[i] = false;
y = SudEst[i].y;
i--;
pereche = true;
}
}
if (pereche == false) {
if (SudEst[SE].x == PozitieXDeIncepere && SudEst[SE].y < PozitieYDeIncepere) {
drumuri--;
SudVest.push_back(SudEst[SE]);
}
}
SE--;
pereche = false;
while (SE >=0 && SudEstBool[SE] == false) {
SE--;
}
drumuri++;
}
while (NV >= 0 && drumuri <= NrDeDrumuri) {
int x = NordVest[NV].x;
for (int i = NV-1; i >= 0; i--) {
if (NordVestBool == false) {
}else if (NordVest[i].x < x) {
NordVestBool[i] == false;
x = NordVest[i].x;
i--;
pereche = true;
}
}
if (pereche == false) {
if (NordVest[NV].x < PozitieXDeIncepere && NordVest[NV].y == PozitieYDeIncepere) {
SudVest.push_back(NordVest[NV]);
drumuri--;
}
}
pereche = false;
NV--;
while (NV >=0 && NordVestBool[NV] == false) {
NV--;
}
drumuri++;
}
while (SV >= 0 && drumuri <= NrDeDrumuri) {
int x = SudVest[SV].x;
for (int i = SV-1; i>=0; i--) {
if (SudVestBool == false) {
}else if (SudVest[i].x < x ) {
SudVestBool[i] = false;
x = SudVest[i].x;
i--;
}
}
SV--;
while (SudVestBool[SV] == false) {
SV--;
}
drumuri++;
}
if (drumuri > NrDeDrumuri) {
return false;
}
else {
return true;
}
}
int main() {
int numarDePoziti;
cin >> numarDePoziti;
cin >> PozitieXDeIncepere >> PozitieYDeIncepere;
vector <Poziti> NordEst, SudEst, NordVest, SudVest;
Poziti ElementPtVectori;
for (int i = 0; i < numarDePoziti; i++) {
int x, y;
cin >> x >> y;
if (x >= PozitieXDeIncepere && y >= PozitieYDeIncepere) {
ElementPtVectori.x = x;
ElementPtVectori.y = y;
NordEst.push_back(ElementPtVectori);
}
if (x >= PozitieXDeIncepere && y < PozitieYDeIncepere) {
ElementPtVectori.x = x;
ElementPtVectori.y = y;
SudEst.push_back(ElementPtVectori);
}
if (x <= PozitieXDeIncepere && y > PozitieYDeIncepere) {
ElementPtVectori.x = x;
ElementPtVectori.y = y;
NordVest.push_back(ElementPtVectori);
}
if (x < PozitieXDeIncepere && y < PozitieYDeIncepere) {
ElementPtVectori.x = x;
ElementPtVectori.y = y;
SudVest.push_back(ElementPtVectori);
}
}
sort(NordEst.begin(), NordEst.end(), [](const Poziti& a, const Poziti& b) {
return a.y < b.y;
});
sort(SudEst.begin(), SudEst.end(), [](const Poziti& a, const Poziti& b) {
return a.x < b.x;
});
sort(NordVest.begin(), NordVest.end(), [](const Poziti& a, const Poziti& b) {
return a.y < b.y;
});
sort(SudVest.begin(), SudVest.end(), [](const Poziti& a, const Poziti& b) {
return a.y > b.y;
});
bitset<50000>NordEstBool, SudEstBool, NordVestBool, SudVestBool;
for (int i = 0; i <= NordEst.size(); i++) {
NordEstBool[i] = 1;
}
for (int i = 0; i <= SudEst.size(); i++) {
SudEstBool[i] = 1;
}
for (int i = 0; i <= NordVest.size(); i++) {
NordVestBool[i] = 1;
}
for (int i = 0; i <= SudVest.size(); i++) {
SudVestBool[i] = 1;
}
int stanga = 1, dreapta = numarDePoziti, rezultat = numarDePoziti;
while (stanga <= dreapta) {
int mijloc = (dreapta + stanga) / 2;
if (EstePosibil(NordEst, SudEst, NordVest, SudVest, NordEstBool, SudEstBool, NordVestBool, SudVestBool,mijloc)) {
rezultat = mijloc;
dreapta = mijloc - 1;
}
else {
stanga = mijloc + 1;
}
}
cout << rezultat;
return 0;
}