oj.uz

답안 #448673

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
448673 2021-07-31T15:09:02 Z vanic The Forest of Fangorn (CEOI14_fangorn) C++14
100 / 100
 679 ms 1316 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];
bool moze[maxm];
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){
			for(int i=0; i<m; i++){
				if(moze[i] && !provjeri(t1, t2, d[x], q[i])){
//					cout << "uklanjam " << i << ' ' << x << ' ' << y << endl;
					moze[i]=0;
				}
			}
			sw[y].push_back({kor[y][ind], -1});
			sw[y].push_back({kor[y][ind+1], 1});
		}
	}
}

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++){
		moze[i]=1;
		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);
	}
	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 || !moze[sw[i][j].second-2]){
					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

# 결과 실행 시간 메모리 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 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 5 ms 332 KB Output is correct
11 Correct 5 ms 332 KB Output is correct
12 Correct 5 ms 332 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 151 ms 580 KB Output is correct
5 Correct 31 ms 332 KB Output is correct
6 Correct 659 ms 768 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 628 ms 904 KB Output is correct
2 Correct 645 ms 1316 KB Output is correct
3 Correct 679 ms 1252 KB Output is correct
4 Correct 280 ms 1256 KB Output is correct