Submission #240639

#	Time	Username	Problem	Language	Result	Execution time	Memory
240639		GREGOIRELC	Hamburg Steak (JOI20_hamburg)	C++14	2 / 100	101 ms	4644 KiB

hamburg

#include <iostream>
#include <vector>

using namespace std;

const int COORD_MAX = 1e9;

struct Coord
{
	int xBas = 0, yBas = 0, xHaut = COORD_MAX + 1, yHaut = COORD_MAX + 1;
	Coord(int _xBas = 0, int _yBas = 0, int _xHaut = COORD_MAX + 1, int _yHaut = COORD_MAX + 1)
	{
		xBas = _xBas;
		yBas = _yBas;
		xHaut = _xHaut;
		yHaut = _yHaut;
	}
	void operator=(Coord &other)
	{
		xBas = other.xBas;
		yBas = other.yBas;
		xHaut = other.xHaut;
		yHaut = other.yHaut;
	}
};

int N, K;
vector<Coord> coordRect;

Coord inter(Coord rect1, Coord rect2)
{
	Coord retour;
	retour.xBas = max(rect1.xBas, rect2.xBas);
	retour.yBas = max(rect1.yBas, rect2.yBas);
	retour.xHaut = min(rect1.xHaut, rect2.xHaut);
	retour.yHaut = min(rect1.yHaut, rect2.yHaut);
	if(retour.xBas > retour.xHaut || retour.yBas > retour.yHaut)
	{
		retour.xBas = -1;
	}
	return retour;
}

int main()
{
	ios::sync_with_stdio(false);

	cin >> N >> K;
	int xBasRect = 0, yBasRect = 0, xHautRect = COORD_MAX + 1, yHautRect = COORD_MAX + 1;
	for(int i = 0; i < N; i++)
	{
		int xBas, yBas, xHaut, yHaut;
		cin >> xBas >> yBas >> xHaut >> yHaut;
		xBasRect = max(xBasRect, xBas);
		yBasRect = max(yBasRect, yBas);
		xHautRect = min(xHaut, xHautRect);
		yHautRect = min(yHaut, yHautRect);
		coordRect.push_back({xBas, yBas, xHaut, yHaut});
	}
	if(K == 1)
	{
		cout << xBasRect << " " << yBasRect << endl;
		return 0;
	}
	Coord rectangle1;
	Coord rectangle2;
	for(int i = 0; i < N; i++)
	{
		for(int j = i + 1; j < N; j++)
		{
			Coord a = inter(coordRect[i], coordRect[j]);
			if(a.xBas == -1)
			{
				rectangle1 = coordRect[i];
				rectangle2 = coordRect[j];
				break;
			}
		}
		if(rectangle1.xBas != 0)
		{
			break;
		}
	}
	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < N; j++)
		{
			Coord a = inter(rectangle1, coordRect[i]);
			Coord b = inter(rectangle2, coordRect[i]);
			if(a.xBas == -1)
			{
				rectangle2 = b;
			}
			else
			{
				rectangle1 = a;
			}
		}
	}
	cout << rectangle1.xBas << " " << rectangle1.yBas << endl;
	cout << rectangle2.xBas << " " << rectangle2.yBas << endl;
}

• Subtask 1: 1 / 1
• Subtask 2: 0 / 1
• Subtask 3: 0 / 3
• Subtask 4: 0 / 6
• Subtask 5: 1 / 1
• Subtask 6: 0 / 3
• Subtask 7: 0 / 6
• Subtask 8: 0 / 79