oj.uz

Submission #448653

# Submission time Handle Problem Language Result Execution time Memory
448653 2021-07-31T11:35:14 Z vanic The Forest of Fangorn (CEOI14_fangorn) C++14
100 / 100
 1332 ms 1256 KB 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cassert>

using namespace std;

const int maxn=2005, maxm=1e4+5;
const double inf=2e18;

pair < int, int > d[maxn];
pair < int, int > q[maxm];
int n, m;

vector < double > kor[4]; // jednadzbe: x=0, y=0, x=w, y=h
vector < pair < double, int > > sw[4];
vector < int > sol;
pair < int, int > pos;
int w, h;

void radi(int x, int y){
	double a, b, c;
	int dx, dy;
	dx=d[x].first-d[y].first;
	dy=d[x].second-d[y].second;
	a=-dy;
	b=dx;
	c=-a*d[x].first-b*d[x].second;
	double sol1, sol2, sol3, sol4;
	if(b==0){
		sol1=-inf;
		sol3=inf;
	}
	else{
		sol1=-c/b;
		sol3=(-c-a*w)/b;
	}
	if(a==0){
		sol2=-inf;
		sol4=inf;
	}
	else{
		sol2=-c/a;
		sol4=(-c-b*h)/a;
	}
//	cout << sol1 << ' ' << sol2 << ' ' << sol3 << ' ' << sol4 << endl;
	if(b==0){
		if(d[x].second<d[y].second){
			kor[0].push_back(sol1);
//			kor[y][2].push_back(sol3);
			kor[2].push_back(sol1);
//			kor[y][0].push_back(sol3);
		}
		else{
			kor[0].push_back(sol3);
//			kor[y][2].push_back(sol1);
			kor[2].push_back(sol3);
//			kor[y][0].push_back(sol1);
		}
	}
	else if(d[x].first<d[y].first){
		kor[0].push_back(sol1);
//		kor[y][2].push_back(sol3);
	}
	else{
		kor[2].push_back(sol3);
//		kor[y][0].push_back(sol1);
	}
	if(a==0){
		if(d[x].first<d[y].first){
			kor[1].push_back(sol2);
//			kor[y][3].push_back(sol4);
			kor[3].push_back(sol2);
//			kor[y][1].push_back(sol4);
		}
		else{
			kor[1].push_back(sol4);
//			kor[y][3].push_back(sol2);
			kor[3].push_back(sol4);
//			kor[y][1].push_back(sol2);
		}
	}
	else if(d[x].second<d[y].second){
		kor[1].push_back(sol2);
//		kor[y][3].push_back(sol4);
	}
	else{
		kor[3].push_back(sol4);
//		kor[y][1].push_back(sol2);
	}
}

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);
}

bool provjeri(pair < double, double > a, pair < double, double > b, pair < double, double > c, pair < double, double > x){
	if(ccw(a, b, c)<0){
		swap(b, c);
	}
	return ccw(a, b, x)>0 && ccw(b, c, x)>0 && ccw(c, a, x)>0;
}

void rijesi(int x, int y){
	sort(kor[y].begin(), kor[y].end());
	pair < double, double > t1, t2;
	if(y==0){
		t1.first=0;
		t2.first=0;
	}
	else if(y==1){
		t1.second=0;
		t2.second=0;
	}
	else if(y==2){
		t1.first=w;
		t2.first=w;
	}
	else{
		t1.second=h;
		t2.second=h;
	}
	int ind=-1;
	for(int i=0; i<(int)kor[y].size()-1; i++){
		if(y==0){
			t1.second=kor[y][i];
			t2.second=kor[y][i+1];
		}
		else if(y==1){
			t1.first=kor[y][i];
			t2.first=kor[y][i+1];
		}
		else if(y==2){
			t1.second=kor[y][i];
			t2.second=kor[y][i+1];
		}
		else{
			t1.first=kor[y][i];
			t2.first=kor[y][i+1];
		}
		if(provjeri(t1, t2, d[x], pos)){
			ind=i;
			break;
		}
	}
	if(kor[y].size()>1){
		sw[y].push_back({kor[y][0], 1});
		sw[y].push_back({kor[y].back(), -1});
		if(ind!=-1){
			sw[y].push_back({kor[y][ind], -1});
			sw[y].push_back({kor[y][ind+1], 1});
		}
	}
}

struct brut{
vector < bool > moze;
vector < int > sol;


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(){
	for(int i=0; i<m; i++){
		moze.push_back(1);
	}
	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;
}

};

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> w >> h;
	cin >> pos.first >> pos.second;
	cin >> m;
	for(int i=0; i<m; i++){
		cin >> q[i].first >> q[i].second;
	}
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> d[i].first >> d[i].second;
		assert(d[i].first!=0 && d[i].second!=0 && d[i].first!=w && d[i].second!=h);
	}
	if(n<=200 && m<=5){
		brut B;
		B.main();
		return 0;
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(i==j){
				continue;
			}
			radi(i, j);
		}
		for(int j=0; j<4; j++){
			rijesi(i, j);
			kor[j].clear();
		}
	}
	for(int i=0; i<m; i++){
		if(q[i].first==0){
			sw[0].push_back({q[i].second, i+2});
		}
		else if(q[i].second==0){
			sw[1].push_back({q[i].first, i+2});
		}
		else if(q[i].first==w){
			sw[2].push_back({q[i].second, i+2});
		}
		else{
			sw[3].push_back({q[i].first, i+2});
		}
	}
	int val;
	for(int i=0; i<4; i++){
		sort(sw[i].begin(), sw[i].end());
		val=0;
		for(int j=0; j<(int)sw[i].size(); j++){
			if(sw[i][j].second<2){
				val+=sw[i][j].second;
			}
			else{
				if(val){
					continue;
				}
				sol.push_back(sw[i][j].second-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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 6 ms 332 KB Output is correct
8 Correct 17 ms 328 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 9 ms 204 KB Output is correct
3 Correct 37 ms 324 KB Output is correct
4 Correct 12 ms 332 KB Output is correct
5 Correct 11 ms 328 KB Output is correct
6 Correct 61 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 39 ms 204 KB Output is correct
10 Correct 930 ms 304 KB Output is correct
11 Correct 1237 ms 324 KB Output is correct
12 Correct 1332 ms 312 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 6 ms 204 KB Output is correct
3 Correct 6 ms 320 KB Output is correct
4 Correct 149 ms 596 KB Output is correct
5 Correct 31 ms 412 KB Output is correct
6 Correct 623 ms 676 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 628 ms 848 KB Output is correct
2 Correct 631 ms 1164 KB Output is correct
3 Correct 627 ms 1256 KB Output is correct
4 Correct 243 ms 1092 KB Output is correct