oj.uz

답안 #420866

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

const int maxn=1e5;
struct point{
	int x, y;
};
int k;
struct solution{
	int a, b, c, d, e, f, g, h, i, j;
	long long area;
	solution():area(4000000000000000003){}
	solution(int a, int b, int c):a(a), b(b), c(c){
		area=(long long)c*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){
		area=(long long)c*c+(long long)f*f;
		if((a+c<=d or d+f<=a) and (b+c<=e or e+f<=b))
			area=4000000000000000003;
	}
	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){
		area=(long long)c*c+(long long)f*f+(long long)i*i;
	}
	bool operator<(const solution& rhs)const{
		return area<rhs.area;
	}
};
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){
		solution ans;
		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;
		//lower left exists
		{
			xs=multiset<int>(sx.begin(), sx.end()), ys=multiset<int>(sy.begin(), sy.end());
			vector<point> capture1=points;
			sort(capture1.begin(), capture1.end(), [&](point a, point b){
				return max(a.x-xmin, a.y-ymin)<max(b.x-xmin, b.y-ymin);
			});
			for(auto i : capture1){
				xs.erase(xs.lower_bound(i.x));
				ys.erase(ys.lower_bound(i.y));
				int x1=xmin, y1=ymin, s1=max({i.x-xmin, i.y-ymin, 1});
				int x2=xs.empty()?2e9:*xs.begin(), y2=ys.empty()?2e9:*ys.begin(), s2=xs.empty()?1:max({*xs.rbegin()-x2, *ys.rbegin()-y2, 1});
				ans=min(ans, solution(x1, y1, s1, x2, y2, s2));
			}
		}
		//upper left exists
		{
			xs=multiset<int>(sx.begin(), sx.end()), ys=multiset<int>(sy.begin(), sy.end());
			vector<point> capture1=points;
			sort(capture1.begin(), capture1.end(), [&](point a, point b){
				return max(a.x-xmin, ymax-a.y)<max(b.x-xmin, ymax-b.y);
			});
			for(auto i : capture1){
				xs.erase(xs.lower_bound(i.x));
				ys.erase(ys.lower_bound(i.y));
				int x1=xmin, y1=ymax, s1=max({i.x-xmin, ymax-i.y, 1});
				y1-=s1;
				int x2=xs.empty()?2e9:*xs.begin(), y2=ys.empty()?2e9:*ys.begin(), s2=xs.empty()?1:max({*xs.rbegin()-x2, *ys.rbegin()-y2, 1});
				ans=min(ans, solution(x1, y1, s1, x2, y2, s2));
			}
		}
		//lower right exists
		{
			xs=multiset<int>(sx.begin(), sx.end()), ys=multiset<int>(sy.begin(), sy.end());
			vector<point> capture1=points;
			sort(capture1.begin(), capture1.end(), [&](point a, point b){
				return max(xmax-a.x, a.y-ymin)<max(xmax-b.x, b.y-ymin);
			});
			for(auto i : capture1){
				xs.erase(xs.lower_bound(i.x));
				ys.erase(ys.lower_bound(i.y));
				int x1=xmax, y1=ymin, s1=max({xmax-i.x, i.y-ymin, 1});
				x1-=s1;
				int x2=xs.empty()?2e9:*xs.begin(), y2=ys.empty()?2e9:*ys.begin(), s2=xs.empty()?1:max({*xs.rbegin()-x2, *ys.rbegin()-y2, 1});
				ans=min(ans, solution(x1, y1, s1, x2, y2, s2));
			}
		}
		printf("%d %d %d\n%d %d %d\n", ans.a, ans.b, ans.c, ans.d, ans.e, ans.f);
	}else if(k==3 and n<=1000){

	}
}

Compilation message

izvanzemaljci.cpp: In function 'int main()':
izvanzemaljci.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
izvanzemaljci.cpp:38:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |    scanf("%d%d", &x, &y);
      |    ~~~~~^~~~~~~~~~~~~~~~
izvanzemaljci.cpp:53:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |    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 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 204 KB Output is correct
7 Correct 28 ms 276 KB Output is correct
8 Correct 29 ms 204 KB Output is correct
9 Correct 29 ms 264 KB Output is correct
10 Correct 29 ms 268 KB Output is correct
11 Correct 28 ms 204 KB Output is correct

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 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 0 ms 204 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

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