oj.uz

답안 #420927

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
420927 2021-06-08T14:57:16 Z Nicholas_Patrick Izvanzemaljci (COI21_izvanzemaljci) C++17
5 / 100
 37 ms 272 KB 
#include <cstdio>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;

const int maxn=1e5;
struct point{
	int x, y;
};
struct compx{
	bool operator()(point a, point b)const{
		if(a.x!=b.x)
			return a.x<b.x;
		return a.y<b.y;
	}
};
struct compy{
	bool operator()(point a, point b)const{
		if(a.y!=b.y)
			return a.y<b.y;
		return a.x<b.x;
	}
};
int k;
struct solution{
	int a, b, c, d, e, f, g, h, i, j;
	int longest;
	solution():longest(2000000001){}
	solution(int a, int b, int c):a(a), b(b), c(c){
		longest=c;
	}
	solution(int a, int b, int c, int d, int e, int f):a(a), b(b), c(c), d(d), e(e), f(f){
		longest=max(c, f);
		if((a+c<=d or d+f<=a) and (b+c<=e or e+f<=b))
			longest=2000000001;
	}
	solution(int a, int b, int c, int d, int e, int f, int g, int h, int i):a(a), b(b), c(c), d(d), e(e), f(f), g(g), h(h), i(i){
		longest=max({c, f, i});
	}
	bool operator<(const solution& rhs)const{
		return longest<rhs.longest;
	}
};
int main(){
	int n;
	scanf("%d%d", &n, &k);
	if(k==1){
		int xmin=1e9, xmax=-1e9, ymin=1e9, ymax=-1e9;
		for(int i=n; i--;){
			int x, y;
			scanf("%d%d", &x, &y);
			xmin=min(xmin, x);
			xmax=max(xmax, x);
			ymin=min(ymin, y);
			ymax=max(ymax, y);
		}
		int s=1;
		s=max(s, xmax-xmin);
		s=max(s, ymax-ymin);
		printf("%d %d %d\n", xmin, ymin, s);
	}else if(k==2){
		vector<point> points(n);
		int xmin=1e9, xmax=-1e9, ymin=1e9, ymax=-1e9;
		for(auto& i : points){
			scanf("%d%d", &i.x, &i.y);
			xmin=min(xmin, i.x);
			xmax=max(xmax, i.x);
			ymin=min(ymin, i.y);
			ymax=max(ymax, i.y);
		}
		// vector<int> sx, sy;
		// for(auto& i : points){
		// 	sx.push_back(i.x);
		// 	sy.push_back(i.y);
		// }
		// sort(sx.begin(), sx.end());
		// sort(sy.begin(), sy.end());
		// multiset<int> xs, ys;
		int best=2e9, x1=-1e9, y1=-1e9, s1=2e9, x2=2.1e9, y2=2.1e9, s2=2e9;
		vector<point> sortx=points, sorty=points;
		sort(sortx.begin(), sortx.end(), [&](point a, point b){
			if(a.x!=b.x)
				return a.x<b.x;
			return a.y<b.y;
		});
		sort(sorty.begin(), sorty.end(), [&](point a, point b){
			if(a.y!=b.y)
				return a.y<b.y;
			return a.x<b.x;
		});
		{
			set<point, compx> sx1, sx2(sortx.begin(), sortx.end());
			set<point, compy> sy1, sy2(sorty.begin(), sorty.end());
			while(not sx2.empty()){
				sx1.insert(*sx2.begin());
				sy1.insert(*sx2.begin());
				sy2.erase(*sx2.begin());
				sx2.erase(sx2.begin());
				int cx1=sx1.rbegin()->x,
					cy1=sy1.begin()->y,
					cs1=max({sx1.rbegin()->x-sx1.begin()->x, sy1.rbegin()->y-sy1.begin()->y, 1});
				cx1-=cs1;
				int cx2=sx2.empty()?2.1e9:sx2.begin()->x,
					cy2=sx2.empty()?2.1e9:sy2.begin()->y,
					cs2=sx2.empty()?1:max({sx2.rbegin()->x-sx2.begin()->x, sy2.rbegin()->y-sy2.begin()->y, 1});
				if((cx1+cs1<cx2 or cx2+cx2<cx1) and (cy1+cs1<cy2 or cy2+cs2<cy1))
					continue;
				if(max(cs1, cs2)<best){
					best=max(cs1, cs2);
					x1=cx1;
					y1=cy1;
					s1=cs1;
					x2=cx2;
					y2=cy2;
					s2=cs2;
				}
			}
		}
		{
			set<point, compx> sx1, sx2(sortx.begin(), sortx.end());
			set<point, compy> sy1, sy2(sorty.begin(), sorty.end());
			while(not sx2.empty()){
				sx1.insert(*sy2.begin());
				sy1.insert(*sy2.begin());
				sx2.erase(*sy2.begin());
				sy2.erase(sy2.begin());
				int cx1=sx1.begin()->x,
					cy1=sy1.rbegin()->y,
					cs1=max({sx1.rbegin()->x-sx1.begin()->x, sy1.rbegin()->y-sy1.begin()->y, 1});
				cy1-=cs1;
				int cx2=sx2.empty()?2.1e9:sx2.begin()->x,
					cy2=sx2.empty()?2.1e9:sy2.begin()->y,
					cs2=sx2.empty()?1:max({sx2.rbegin()->x-sx2.begin()->x, sy2.rbegin()->y-sy2.begin()->y, 1});
				if((cx1+cs1<cx2 or cx2+cx2<cx1) and (cy1+cs1<cy2 or cy2+cs2<cy1))
					continue;
				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);
	}else if(k==3 and n<=1000){
		vector<point> points(n);
		int xmin=1e9, xmax=-1e9, ymin=1e9, ymax=-1e9;
		for(auto& i : points){
			scanf("%d%d", &i.x, &i.y);
			xmin=min(xmin, i.x);
			xmax=max(xmax, i.x);
			ymin=min(ymin, i.y);
			ymax=max(ymax, i.y);
		}
		vector<int> sx, sy;
		for(auto& i : points){
			sx.push_back(i.x);
			sy.push_back(i.y);
		}
		sort(sx.begin(), sx.end());
		sort(sy.begin(), sy.end());
		multiset<int> xs, ys;
		int best=2e9, x1=-1e9, y1=-1e9, s1=2e9, x2=2e9, y2=2e9, s2=2e9;
	}
}

Compilation message

izvanzemaljci.cpp: In function 'int main()':
izvanzemaljci.cpp:167:7: warning: unused variable 'best' [-Wunused-variable]
  167 |   int best=2e9, x1=-1e9, y1=-1e9, s1=2e9, x2=2e9, y2=2e9, s2=2e9;
      |       ^~~~
izvanzemaljci.cpp:167:17: warning: unused variable 'x1' [-Wunused-variable]
  167 |   int best=2e9, x1=-1e9, y1=-1e9, s1=2e9, x2=2e9, y2=2e9, s2=2e9;
      |                 ^~
izvanzemaljci.cpp:167:26: warning: unused variable 'y1' [-Wunused-variable]
  167 |   int best=2e9, x1=-1e9, y1=-1e9, s1=2e9, x2=2e9, y2=2e9, s2=2e9;
      |                          ^~
izvanzemaljci.cpp:167:35: warning: unused variable 's1' [-Wunused-variable]
  167 |   int best=2e9, x1=-1e9, y1=-1e9, s1=2e9, x2=2e9, y2=2e9, s2=2e9;
      |                                   ^~
izvanzemaljci.cpp:167:43: warning: unused variable 'x2' [-Wunused-variable]
  167 |   int best=2e9, x1=-1e9, y1=-1e9, s1=2e9, x2=2e9, y2=2e9, s2=2e9;
      |                                           ^~
izvanzemaljci.cpp:167:51: warning: unused variable 'y2' [-Wunused-variable]
  167 |   int best=2e9, x1=-1e9, y1=-1e9, s1=2e9, x2=2e9, y2=2e9, s2=2e9;
      |                                                   ^~
izvanzemaljci.cpp:167:59: warning: unused variable 's2' [-Wunused-variable]
  167 |   int best=2e9, x1=-1e9, y1=-1e9, s1=2e9, x2=2e9, y2=2e9, s2=2e9;
      |                                                           ^~
izvanzemaljci.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
izvanzemaljci.cpp:52:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |    scanf("%d%d", &x, &y);
      |    ~~~~~^~~~~~~~~~~~~~~~
izvanzemaljci.cpp:66:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |    scanf("%d%d", &i.x, &i.y);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~
izvanzemaljci.cpp:153:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |    scanf("%d%d", &i.x, &i.y);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 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 1 ms 204 KB Output is correct
7 Correct 37 ms 204 KB Output is correct
8 Correct 28 ms 204 KB Output is correct
9 Correct 29 ms 204 KB Output is correct
10 Correct 36 ms 204 KB Output is correct
11 Correct 29 ms 272 KB Output is correct

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -