oj.uz

Submission #59300

# Submission time Handle Problem Language Result Execution time Memory
59300 2018-07-21T12:39:54 Z tmwilliamlin168 The Forest of Fangorn (CEOI14_fangorn) C++14
100 / 100
 118 ms 1548 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll, ll>
#define fi first
#define se second

const int mxC=1e4, mxN=2e3;
int c, n, m;
ll w, h, sx, sy, cx[mxC], cy[mxC], tx[mxN], ty[mxN];
bool a1[mxC];

inline bool fc(pll a, pll b) {
	return a.fi*b.se<b.fi*a.se;
}

inline pll af(ll dx, ll dy) {
	return dy<0?pll(dx-abs(dx)+dy, abs(dx)-dy):pll(abs(dx)-dx+dy, abs(dx)+dy);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> w >> h >> sx >> sy >> c;
	for(int i=0; i<c; ++i)
		cin >> cx[i] >> cy[i];
	cin >> n;
	for(int i=0; i<n; ++i)
		cin >> tx[i] >> ty[i];
	memset(a1, 1, c);
	for(int i=0; i<n; ++i) {
		pll pa=af(sx-tx[i], sy-ty[i]), pb={-3, 1}, pc={3, 1};
		for(int j=0; j<n; ++j) {
			if(j==i)
				continue;
			pll pd=af(tx[i]-tx[j], ty[i]-ty[j]);
			if(fc(pa, pd)&&fc(pd, pc))
				pc=pd;
			else if(fc(pd, pa)&&fc(pb, pd))
				pb=pd;
		}
//		cout << (double)pa.fi/pa.se << " " << (double)pb.fi/pb.se << " " << (double)pc.fi/pc.se << endl;
		if(pb==pll(-3, 1)||pc==pll(3, 1)) {
			if(pb.fi==-3) {
				for(int j=0; j<n; ++j) {
					if(j==i)
						continue;
					pll pd=af(tx[i]-tx[j], ty[i]-ty[j]);
					if(fc(pb, pd))
						pb=pd;
				}
			} else {
				for(int j=0; j<n; ++j) {
					if(j==i)
						continue;
					pll pd=af(tx[i]-tx[j], ty[i]-ty[j]);
					if(fc(pd, pc))
						pc=pd;
				}
			}
			for(int j=0; j<c; ++j) {
				if(!a1[j])
					continue;
				pll pd=af(cx[j]-tx[i], cy[j]-ty[i]);
				a1[j]=fc(pb, pd)||fc(pd, pc);
			}
		} else {
			for(int j=0; j<c; ++j) {
				if(!a1[j])
					continue;
//				cout << cx[j] << " " << tx[i
				pll pd=af(cx[j]-tx[i], cy[j]-ty[i]);
//				if(j==1)
//				cout << (double)pd.fi/pd.se << endl;
				a1[j]=fc(pb, pd)&&fc(pd, pc);
			}
		}
	}
	for(int i=0; i<c; ++i)
		m+=a1[i];
	cout << m << "\n";
	for(int i=0; i<c; ++i)
		if(a1[i])
			cout << i+1 << " ";
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 3 ms 380 KB Output is correct
3 Correct 3 ms 552 KB Output is correct
4 Correct 2 ms 552 KB Output is correct
5 Correct 3 ms 552 KB Output is correct
6 Correct 2 ms 568 KB Output is correct
7 Correct 2 ms 676 KB Output is correct
8 Correct 3 ms 676 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 676 KB Output is correct
2 Correct 2 ms 708 KB Output is correct
3 Correct 3 ms 756 KB Output is correct
4 Correct 3 ms 756 KB Output is correct
5 Correct 3 ms 756 KB Output is correct
6 Correct 3 ms 756 KB Output is correct
7 Correct 3 ms 756 KB Output is correct
8 Correct 3 ms 756 KB Output is correct
9 Correct 3 ms 756 KB Output is correct
10 Correct 3 ms 756 KB Output is correct
11 Correct 4 ms 756 KB Output is correct
12 Correct 3 ms 756 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 756 KB Output is correct
2 Correct 3 ms 816 KB Output is correct
3 Correct 2 ms 816 KB Output is correct
4 Correct 11 ms 816 KB Output is correct
5 Correct 6 ms 816 KB Output is correct
6 Correct 57 ms 816 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 816 KB Output is correct
2 Correct 118 ms 1288 KB Output is correct
3 Correct 53 ms 1392 KB Output is correct
4 Correct 66 ms 1548 KB Output is correct