Cod sursa(job #3302675)

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