oj.uz

Submission #421168

# Submission time Handle Problem Language Result Execution time Memory
421168 2021-06-08T19:48:48 Z Nicholas_Patrick Izvanzemaljci (COI21_izvanzemaljci) C++17
5 / 100
 51 ms 4628 KB 
#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);
		return 0;
	}
	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(cx1+cs1<cx2 or cy1+cs1<cy2 or cx2+cs2<cx1 or cy2+cs2<cy1)
				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(cx1+cs1<cx2 or cy1+cs1<cy2 or cx2+cs2<cx1 or cy2+cs2<cy1)
				if(max(cs1, cs2)<best){
					best=max(cs1, cs2);
					x1=cx1;
					y1=cy1;
					s1=cs1;
					x2=cx2;
					y2=cy2;
					s2=cs2;
				}
			}
		}
	}
	if(k==2){
		printf("%d %d %d\n%d %d %d\n", x1, y1, s1, x2, y2, s2);
	}
}

Compilation message

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 30 ms 3104 KB Output is correct
8 Correct 30 ms 3012 KB Output is correct
9 Correct 30 ms 2972 KB Output is correct
10 Correct 30 ms 2968 KB Output is correct
11 Correct 30 ms 2976 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 272 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Incorrect 51 ms 4628 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -