oj.uz

Submission #448648

# Submission time Handle Problem Language Result Execution time Memory
448648 2021-07-31T10:55:08 Z vanic The Forest of Fangorn (CEOI14_fangorn) C++14
10 / 100
 1508 ms 332 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);
	if(sijeku(x, y, a, e) || sijeku(x, y, a, f)){
		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';
	sort(sol.begin(), sol.end());
	for(int i=0; i<(int)sol.size(); i++){
		cout << sol[i] << ' ';
	}
	cout << '\n';
	return 0;
}

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 0 ms 204 KB Output isn't correct
4 Correct 1 ms 204 KB Output is correct
5 Incorrect 0 ms 204 KB Output isn't correct
6 Incorrect 0 ms 204 KB Output isn't correct
7 Correct 5 ms 204 KB Output is correct
8 Incorrect 12 ms 308 KB Output isn't correct

Subtask #2
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 204 KB Output is correct
2 Correct 10 ms 204 KB Output is correct
3 Correct 47 ms 204 KB Output is correct
4 Correct 11 ms 204 KB Output is correct
5 Correct 11 ms 308 KB Output is correct
6 Correct 59 ms 204 KB Output is correct
7 Incorrect 1 ms 204 KB Output isn't correct
8 Incorrect 1 ms 204 KB Output isn't correct
9 Correct 34 ms 204 KB Output is correct
10 Incorrect 882 ms 308 KB Output isn't correct
11 Incorrect 867 ms 296 KB Output isn't correct
12 Correct 1508 ms 204 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 Incorrect 5 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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