Pagini recente » Cod sursa (job #1727715) | Cod sursa (job #589302) | Cod sursa (job #3120855) | Cod sursa (job #2314041) | Cod sursa (job #3302675)
#include <fstream>
//#include <iostream>
#include <algorithm>
#include <vector>
#include <bitset>
using namespace std;
ifstream cin("pachete.in");
ofstream cout("pachete.out");
struct Poziti {
int x;
int y;
};
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 = 0, SE = 0, NV = 0, SV = 0;
while (NE <NordEst.size() && drumuri <= NrDeDrumuri) {
int x = NordEst[NE].x;
int y = NordEst[NE].y;
for (int i = NE+1; i < NordEst.size(); i++) {
if (NordEstBool == false) {
}else if (NordEst[i].x >= x && NordEst[i].y >= y) {
NordEstBool = false;
x = NordEst[i].x;
y = NordEst[i].y;
i++;
}
}
NE++;
while (NordEstBool[NE] == false) {
NE++;
}
drumuri++;
}
while (SE < SudEst.size() && drumuri <= NrDeDrumuri) {
int x = SudEst[SE].x;
int y = SudEst[SE].y;
for (int i = SE+1; i < SudEst.size(); i++) {
if (SudEstBool == false) {
}else if (SudEst[i].x >= x && SudEst[i].y <= y) {
SudEstBool[i] = false;
x = SudEst[i].x;
y = SudEst[i].y;
i++;
}
}
SE++;
while (SudEstBool[SE] == false) {
SE++;
}
drumuri++;
}
while (NV < NordVest.size() && drumuri <= NrDeDrumuri) {
int x = NordVest[NV].x;
int y = NordVest[NV].y;
for (int i = NV+1; i < NordVest.size(); i++) {
if (NordVestBool == false) {
}else if (NordVest[i].x <= x && NordVest[i].y >= y) {
NordVestBool[i] == false;
x = NordVest[i].x;
y = NordVest[i].y;
i++;
}
}
NV++;
while (NordVestBool[NV] == false) {
NV++;
}
drumuri++;
}
while (SV < SudVest.size() && drumuri <= NrDeDrumuri) {
int x = SudVest[SV].x;
int y = SudVest[SV].y;
for (int i = SV+1; i < SudVest.size(); i++) {
if (SudVestBool == false) {
}else if (SudVest[i].x <= x && SudVest[i].y <= y) {
SudVestBool[i] = false;
x = SudVest[i].x;
y = SudVest[i].y;
i++;
}
}
SV++;
while (SudVestBool[SV] == false) {
SV++;
}
drumuri++;
}
if (drumuri > NrDeDrumuri) {
return false;
}
else {
return true;
}
}
int main() {
int numarDePoziti;
cin >> numarDePoziti;
int PozitieXDeIncepere, PozitieYDeIncepere,PozNordEst = 0, PozSudEst = 0, PozNordVest = 0, PozSudVest = 0;;
cin >> PozitieXDeIncepere >> PozitieYDeIncepere;
vector <Poziti> NordEst(numarDePoziti),SudEst(numarDePoziti),NordVest(numarDePoziti),SudVest(numarDePoziti);
for (int i = 0; i < numarDePoziti; i++) {
int x, y;
cin >> x >> y;
if (x >= PozitieXDeIncepere && y >= PozitieYDeIncepere) {
NordEst[PozNordEst].x = x;
NordEst[PozNordEst].y = y;
PozNordEst++;
}
if (x >= PozitieXDeIncepere && y <= PozitieYDeIncepere) {
SudEst[PozSudEst].x = x;
SudEst[PozSudEst].y = y;
PozSudEst++;
}
if (x <= PozitieXDeIncepere && y >= PozitieYDeIncepere) {
NordVest[PozNordVest].x = x;
NordVest[PozNordVest].y = y;
PozNordVest++;
}
if (x <= PozitieXDeIncepere && y <= PozitieYDeIncepere) {
SudVest[PozSudVest].x = x;
SudVest[PozSudVest].y = y;
PozSudVest++;
}
}
NordEst.resize(PozNordEst);
SudEst.resize(PozSudEst);
NordVest.resize(PozNordVest);
SudVest.resize(PozSudVest);
bitset<50000>NordEstBool, SudEstBool, NordVestBool, SudVestBool;
for (int i = 0; i <= PozNordEst; i++) {
NordEstBool[i] = 1;
}
for (int i = 0; i <= PozSudEst; i++) {
SudEstBool[i] = 1;
}
for (int i = 0; i <= PozNordVest; i++) {
NordVestBool[i] = 1;
}
for (int i = 0; i <= PozSudVest; 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;
}