oj.uz

Submission #448651

# Submission time Handle Problem Language Result Execution time Memory
448651 2021-07-31T11:30:11 Z vanic The Forest of Fangorn (CEOI14_fangorn) C++14
50 / 100
 1519 ms 460 KB 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

const int maxn=205, maxm=10;

pair < int, int > d[maxn];
pair < int, int > q[maxm];
bool moze[maxm];
vector < int > sol;
pair < int, int > pos;
int w, h;


double ccw(pair < double, double > a, pair < double, double > b, pair < double, double > c){
	return a.first*(b.second-c.second)+b.first*(c.second-a.second)+c.first*(a.second-b.second);
}

pair < double, double > tocka(pair < double, double > x, pair < double, double > y){
	double a, b, c;
	double dx, dy;
	dx=x.first-y.first;
	dy=x.second-y.second;
	a=-dy;
	b=dx;
	c=-a*x.first-b*x.second;
	double x1, y2, y1, x2;
	if(x.first==y.first){
		if(x.second>y.second){
			return {x.first, h};
		}
		else{
			return {x.first, 0};
		}
	}
	else if(x.second==y.second){
		if(x.first>y.first){
			return {w, x.second};
		}
		else{
			return {0, x.second};
		}
	}
	if(x.first>y.first){
		x1=w;
	}
	else{
		x1=0;
	}
	if(x.second>y.second){
		y2=h;
	}
	else{
		y2=0;
	}
	y1=(-a*x1-c)/b;
	x2=(-b*y2-c)/a;
	if(abs(x1-x.first)<abs(x2-x.first)){
		return {x1, y1};
	}
	return {x2, y2};
}

bool sijeku(pair < double, double > a, pair < double, double > b, pair < double, double > x, pair < double, double > y){
	double c1, c2, c3, c4;
	c1=ccw(a, b, x);
	c2=ccw(a, b, y);
	c3=ccw(x, y, a);
	c4=ccw(x, y, b);
	if((c1<=0 && c2>=0) || (c1>=0 && c2<=0)){
		if((c3>=0 && c4<=0) || (c3<=0 && c4>=0)){
			return 1;
		}
	}
	return 0;
}


bool provjeri(pair < double, double > a, pair < double, double > b, pair < double, double > c, pair < double, double > x, pair < double, double > y){
	pair < double, double > e, f;
	e=tocka(a, b);
	f=tocka(a, c);
	int br=0;
	br+=sijeku(x, y, a, e);
	br+=sijeku(x, y, a, f);
	if(br&1){
		return 0;
	}
	return 1;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> w >> h;
	cin >> pos.first >> pos.second;
	int n, m;
	cin >> m;
	for(int i=0; i<m; i++){
		cin >> q[i].first >> q[i].second;
		moze[i]=1;
	}
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> d[i].first >> d[i].second;
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(i==j){
				continue;
			}
			for(int k=0; k<n; k++){
				if(k==i || k==j){
					continue;
				}
				for(int l=0; l<m; l++){
					if(moze[l] && !provjeri(d[i], d[j], d[k], pos, q[l])){
						moze[l]=0;
					}
				}
			}
		}
	}
	for(int i=0; i<m; i++){
		if(moze[i]){
			sol.push_back(i+1);
		}
	}
	cout << sol.size() << '\n';
	for(int i=0; i<(int)sol.size(); i++){
		cout << sol[i] << ' ';
	}
	cout << '\n';
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory 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 1 ms 204 KB Output is correct
5 Correct 1 ms 248 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 5 ms 204 KB Output is correct
8 Correct 20 ms 204 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 204 KB Output is correct
2 Correct 13 ms 204 KB Output is correct
3 Correct 45 ms 204 KB Output is correct
4 Correct 13 ms 204 KB Output is correct
5 Correct 11 ms 316 KB Output is correct
6 Correct 62 ms 296 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 35 ms 296 KB Output is correct
10 Correct 1010 ms 296 KB Output is correct
11 Correct 1403 ms 328 KB Output is correct
12 Correct 1519 ms 292 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 7 ms 204 KB Output is correct
3 Correct 7 ms 204 KB Output is correct
4 Runtime error 1 ms 332 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -