Submission #103667

#	Time	Username	Problem	Language	Result	Execution time	Memory
103667		Shtef	Pick (COI18_pick)	C++14	10 / 100	3 ms	384 KiB

pick

#include <iostream>
#include <vector>
#include <cmath>
#include <utility>

using namespace std;

typedef long double ld;
typedef pair <int, int> pii;
#define x first
#define y second
#define mp make_pair

int a[4], n;
vector <pii> sad, ans;
bool je[105][105];
ld naj;
const ld inf = (ld)1e15;

ld povrsina(){
	ld ret = 0;
	for(int i = 0 ; i < n - 1 ; ++i){
		ret = (ret + sad[i].x * sad[i + 1].y - sad[i + 1].x * sad[i].y);
	}
	ret = abs(ret) / 2;
	return ret;
}

int koji(int x, int y){
	if(!x)
		return 1;
	if(!y)
		return 0;
	if(x == y)
		return 2;
	return 3;
}

void rek(int kolko, int x, int y){
	if(kolko == n){
		if(x || y)
			return;
		ld t = povrsina();
		if(t < naj){
			naj = t;
			ans = sad;
		}
		return;
	}
	for(int i = -1 ; i <= 1 ; ++i){
		for(int j = -1 ; j <= 1 ; ++j){
			if(!i && !j)
				continue;
			int di = koji(i, j);
			if(!a[di])
				continue;
			int nx = x + i, ny = y + j;
			if(je[nx + 50][ny + 50])
				continue;
			je[nx + 50][ny + 50] = 1;
			a[di]--;
			sad.push_back(mp(nx, ny));
			rek(kolko + 1, nx, ny);
			je[nx + 50][ny + 50] = 0;
			a[di]++;
			sad.pop_back();
		}
	}
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
for(int i = 0 ; i < 4 ; ++i){
	cin >> a[i];
	n += a[i];
}
int x = 0, y = 0;
if(!a[0] && !a[1]){
	cout << 0 << ' ' << 0 << endl;
	for(int i = 0 ; i < a[2] / 2 ; ++i){
		x++;
		y++;
		if(!x && !y)
			continue;
		cout << x << ' ' << y << endl;
	}
	x--;
	y++;
	if(x || y){
		cout << x << ' ' << y << endl;
	}
	for(int i = 0 ; i < a[2] / 2 - 1 ; ++i){
		x--;
		y--;
		if(!x && !y)
			continue;
		cout << x << ' ' << y << endl;
	}
	for(int i = 0 ; i < a[3] / 2 - 1 ; ++i){
		x--;
		y++;
		if(!x && !y)
			continue;
		cout << x << ' ' << y << endl;
	}
	x--;
	y--;
	if(x || y){
		cout << x << ' ' << y << endl;
	}
	for(int i = 0 ; i < a[3] / 2 ; ++i){
		x++;
		y--;
		if(!x && !y)
			continue;
		cout << x << ' ' << y << endl;
	}
}
else if(!a[2] && !a[3]){
	cout << 0 << ' ' << 0 << endl;
	for(int i = 0 ; i < a[0] / 2 ; ++i){
		x++;
		if(!x && !y)
			continue;
		cout << x << ' ' << y << endl;
	}
	for(int i = 0 ; i < a[1] / 2 ; ++i){
		y++;
		if(!x && !y)
			continue;
		cout << x << ' ' << y << endl;
	}
	x--;
	if(x || y){
		cout << x << ' ' << y << endl;
	}
	for(int i = 0 ; i < a[1] / 2 - 1 ; ++i){
		y--;
		if(!x && !y)
			continue;
		cout << x << ' ' << y << endl;
	}
	for(int i = 0 ; i < a[0] / 2 - 1 ; ++i){
		x--;
		if(!x && !y)
			continue;
		cout << x << ' ' << y << endl;
	}
}
else{
	sad.push_back(mp(0, 0));
	je[0][0] = 1;
	naj = inf;
	rek(0, 0, 0);
	for(int i = 0 ; i < n ; ++i){
		cout << ans[i].x << ' ' << ans[i].y << endl;
	}
}

return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 20