Submission #421162

#	Time	Username	Problem	Language	Result	Execution time	Memory
421162		Nicholas_Patrick	Izvanzemaljci (COI21_izvanzemaljci)	C++17	5 / 100	62 ms	2600 KiB

izvanzemaljci

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

struct point{
	int x, y;
};
struct compx{
	bool operator()(point a, point b)const{
		return a.x<b.x;
	}
};
int main(){
	int n, k;
	scanf("%d%d", &n, &k);
	vector<point> points(n);
	for(auto& i : points)
		scanf("%d%d", &i.x, &i.y);
	int minx=1e9, maxx=-1e9, miny=1e9, maxy=-1e9;
	for(auto i : points){
		minx=min(minx, i.x);
		maxx=max(maxx, i.x);
		miny=min(miny, i.y);
		maxy=max(maxy, i.y);
	}
	int l=max({maxx-minx, maxy-miny, 1});
	if(k==1){
		printf("%d %d %d\n", minx, miny, l);
	}else if(k==2){
		int best=l, x1=minx, y1=miny, s1=l, x2=2.1e9, y2=2.1e9, s2=1;
		{
			sort(points.begin(), points.end(), [&](point a, point b){
				return a.x<b.x;
			});
			vector<int> pmax(n+1), smax(n+1), pmin(n+1), smin(n+1);
			pmax[0]=-1e9, pmin[0]=1e9;
			for(int i=0; i<n; i++){
				pmax[i+1]=max(pmax[i], points[i].y);
				pmin[i+1]=min(pmin[i], points[i].y);
			}
			smax[n]=-1e9, smin[n]=1e9;
			for(int i=n; i--;){
				smax[i]=max(smax[i+1], points[i].y);
				smin[i]=min(smin[i+1], points[i].y);
			}
			for(int i=1; i<n; i++){
				if(points[i-1].x<points[i].x){
					int cx1, cy1, cs1, cx2, cy2, cs2;
					cx1=points[i-1].x;
					cy1=pmin[i];
					cs1=max({points[i-1].x-points[0].x, pmax[i]-pmin[i], 1});
					cx1-=cs1;
					cx2=points[i].x;
					cy2=smin[i];
					cs2=max({points[n-1].x-points[i].x, smax[i]-smin[i], 1});
					if(max(cs1, cs2)<best){
						best=max(cs1, cs2);
						x1=cx1;
						y1=cy1;
						s1=cs1;
						x2=cx2;
						y2=cy2;
						s2=cs2;
					}
				}
			}
		}
		{
			sort(points.begin(), points.end(), [&](point a, point b){
				return a.y<b.y;
			});
			vector<int> pmax(n+1), smax(n+1), pmin(n+1), smin(n+1);
			pmax[0]=-1e9, pmin[0]=1e9;
			for(int i=0; i<n; i++){
				pmax[i+1]=max(pmax[i], points[i].x);
				pmin[i+1]=min(pmin[i], points[i].x);
			}
			smax[n]=-1e9, smin[n]=1e9;
			for(int i=n; i--;){
				smax[i]=max(smax[i+1], points[i].x);
				smin[i]=min(smin[i+1], points[i].x);
			}
			for(int i=1; i<n; i++){
				if(points[i-1].y<points[i].y){
					int cy1, cx1, cs1, cy2, cx2, cs2;
					cx1=pmin[i];
					cy1=points[i-1].y;
					cs1=max({points[i-1].y-points[0].y, pmax[i]-pmin[i], 1});
					cy1-=cs1;
					cx2=smin[i];
					cy2=points[i].y;
					cs2=max({points[n-1].y-points[i].y, smax[i]-smin[i], 1});
					if(max(cs1, cs2)<best){
						best=max(cs1, cs2);
						x1=cx1;
						y1=cy1;
						s1=cs1;
						x2=cx2;
						y2=cy2;
						s2=cs2;
					}
				}
			}
		}
		printf("%d %d %d\n%d %d %d\n", x1, y1, s1, x2, y2, s2);
	}
}

Compilation message (stderr)

izvanzemaljci.cpp: In function 'int main()':
izvanzemaljci.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
izvanzemaljci.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |   scanf("%d%d", &i.x, &i.y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 21
• Subtask 3: 0 / 12
• Subtask 4: 0 / 30
• Subtask 5: 0 / 32