Cod sursa(job #3299010)

Utilizator gilbusJoita Cristian gilbus Data 3 iunie 2025 17:32:50
Problema Pachete Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.53 kb
#include <fstream>
#include <algorithm>
#include <vector>
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,int NrDeDrumuri) {
	int drumuri = 0;
	while (NordEst.size() > 1 && drumuri <= NrDeDrumuri) {
		int x = NordEst[0].x;
		int y = NordEst[0].y;
		for (int i = 1; i < NordEst.size(); i++) {
			if (NordEst[i].x <= x && NordEst[i].y <= y) {
				NordEst.erase(
					remove_if(NordEst.begin(), NordEst.end(), [&](const Poziti& p) {
						return p.x == x && p.y == y;
						}),
					NordEst.end()
				);
			}
		}
		NordEst.erase(NordEst.begin());
		drumuri++;
	}
	while (SudEst.size() > 1 && drumuri <= NrDeDrumuri) {
		int x = SudEst[0].x;
		int y = SudEst[0].y;
		for (int i = 1; i < SudEst.size(); i++) {
			if (SudEst[i].x <= x && SudEst[i].y >= y) {
				SudEst.erase(
					remove_if(SudEst.begin(), SudEst.end(), [&](const Poziti& p) {
						return p.x == x && p.y == y;
						}),
					SudEst.end()
				);
			}
		}
		SudEst.erase(SudEst.begin());
		drumuri++;
	}
	while (NordVest.size() > 1 && drumuri <= NrDeDrumuri) {
		int x = NordVest[0].x;
		int y = NordVest[0].y;
		for (int i = 1; i < NordVest.size(); i++) {
			if (NordVest[i].x >= x && NordVest[i].y <= y) {
				NordVest.erase(
					remove_if(NordVest.begin(), NordVest.end(), [&](const Poziti& p) {
						return p.x == x && p.y == y;
						}),
					NordVest.end()
				);
			}
		}
		NordVest.erase(NordVest.begin());
		drumuri++;
	}
	while (SudVest.size() > 1 && drumuri <= NrDeDrumuri) {
		int x = SudVest[0].x;
		int y = SudVest[0].y;
		for (int i = 1; i < SudVest.size(); i++) {
			if (SudVest[i].x >= x && SudVest[i].y >= y) {
				SudVest.erase(
					remove_if(SudVest.begin(), SudVest.end(), [&](const Poziti& p) {
						return p.x == x && p.y == y;
						}),
					SudVest.end()
				);
			}
		}
		SudVest.erase(SudVest.begin());
		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 + 1);
	SudEst.resize(PozSudEst + 1);
	NordVest.resize(PozNordVest + 1);
	SudVest.resize(PozSudVest + 1);
	int stanga = 1, dreapta = numarDePoziti, rezultat = numarDePoziti;
	while (stanga <= dreapta) {
		int mijloc = (dreapta + stanga) / 2;
		if (EstePosibil(NordEst, SudEst, NordVest, SudVest, mijloc)) {
			rezultat = mijloc;
			dreapta = mijloc - 1;
		}
		else {
			stanga = mijloc + 1;
		}
	}
	cout << rezultat;
	return 0;
}