Cod sursa(job #3303901)

Utilizator fantomcristi fantom Data 18 iulie 2025 21:01:56
Problema Pachete Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.86 kb
#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;
}