Submission #448651

#	Time	Username	Problem	Language	Result	Execution time	Memory
448651		vanic	The Forest of Fangorn (CEOI14_fangorn)	C++14	50 / 100	1519 ms	460 KiB

fangorn

#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 / 30
• Subtask 2: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 20