oj.uz

Submission #103667

# Submission time Handle Problem Language Result Execution time Memory
103667 2019-04-01T23:27:55 Z Shtef Pick (COI18_pick) C++14
10 / 100
 3 ms 384 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB not a simple polygon
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB not a simple polygon
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB not a simple polygon
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB not a simple polygon
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB not a simple polygon
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Incorrect 2 ms 384 KB not a simple polygon
10 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Incorrect 2 ms 384 KB not a simple polygon
10 Halted 0 ms 0 KB -

Subtask #10
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Incorrect 2 ms 384 KB not a simple polygon
10 Halted 0 ms 0 KB -