Submission #420863

#	Time	Username	Problem	Language	Result	Execution time	Memory
420863		Nicholas_Patrick	Izvanzemaljci (COI21_izvanzemaljci)	C++17	5 / 100	36 ms	276 KiB

izvanzemaljci

#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;
	}
	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()?0:*xs.begin(), y2=ys.empty()?0:*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()?0:*xs.begin(), y2=ys.empty()?0:*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()?0:*xs.begin(), y2=ys.empty()?0:*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 (stderr)

izvanzemaljci.cpp: In function 'int main()':
izvanzemaljci.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
izvanzemaljci.cpp:36:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |    scanf("%d%d", &x, &y);
      |    ~~~~~^~~~~~~~~~~~~~~~
izvanzemaljci.cpp:51:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |    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