oj.uz

Submission #25715

# Submission time Handle Problem Language Result Execution time Memory
25715 2017-06-23T19:02:05 Z gs14004 The Forest of Fangorn (CEOI14_fangorn) C++11
100 / 100
 286 ms 2124 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

pi s, camp[10005], tree[2005];
int c, n;
bool ok[10005];

bool ccw(pi a, pi b, pi c){
	int dx1 = b.first - a.first;
	int dy1 = b.second - a.second;
	int dx2 = c.first - a.first;
	int dy2 = c.second - a.second;
	return 1ll * dx1 * dy2 > 1ll * dy1 * dx2;
}

void solve(int p){
	vector<pi> ccwl, ccwh;
	for(int i=0; i<n; i++){
		if(p == i) continue;
		if(ccw(s, tree[p], tree[i])){
			ccwl.push_back(tree[i]);
		}
		else{
			ccwh.push_back(tree[i]);
		}
	}
	auto cmp = [&](const pi &a, const pi &b){
		return ccw(tree[p], a, b);
	};
	if(ccwl.empty()){
		pi st = *min_element(ccwh.begin(), ccwh.end(), cmp);
		pi ed = *max_element(ccwh.begin(), ccwh.end(), cmp);
		for(int i=0; i<c; i++){
			if(ccw(st, tree[p], camp[i]) && !ccw(ed, tree[p], camp[i])){
				ok[i] = 0;
			}
		}
		return;
	}
	else if(ccwh.empty()){
		pi st = *min_element(ccwl.begin(), ccwl.end(), cmp);
		pi ed = *max_element(ccwl.begin(), ccwl.end(), cmp);
		for(int i=0; i<c; i++){
			if(ccw(st, tree[p], camp[i]) && !ccw(ed, tree[p], camp[i])){
				ok[i] = 0;
			}
		}
		return;
	}
	pi t = *min_element(ccwl.begin(), ccwl.end(), cmp);
	for(int i=0; i<c; i++){
		if(!ccw(s, tree[p], camp[i]) && ccw(t, tree[p], camp[i])){
			ok[i] = 0;
		}
	}
	t = *max_element(ccwh.begin(), ccwh.end(), cmp);
	for(int i=0; i<c; i++){
		if(ccw(s, tree[p], camp[i]) && !ccw(t, tree[p], camp[i])){
			ok[i] = 0;
		}
	}
}

int main(){
	cin >> c >> n >> s.first >> s.second;
	cin >> c;
	for(int i=0; i<c; i++){
		cin >> camp[i].first >> camp[i].second;
	}
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> tree[i].first >> tree[i].second;
	}
	fill(ok, ok + c, true);
	for(int i=0; i<n; i++){
		solve(i);
	}
	printf("%d\n",count(ok, ok + c, true));
	for(int i=0; i<c; i++){
		if(ok[i]) printf("%d ",i+1);
	}
}

Compilation message

fangorn.cpp: In function 'int main()':
fangorn.cpp:98:39: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::iterator_traits<bool*>::difference_type {aka long int}' [-Wformat=]
  printf("%d\n",count(ok, ok + c, true));
                                       ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2124 KB Output is correct
2 Correct 0 ms 2124 KB Output is correct
3 Correct 0 ms 2124 KB Output is correct
4 Correct 0 ms 2124 KB Output is correct
5 Correct 0 ms 2124 KB Output is correct
6 Correct 0 ms 2124 KB Output is correct
7 Correct 0 ms 2124 KB Output is correct
8 Correct 0 ms 2124 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2124 KB Output is correct
2 Correct 0 ms 2124 KB Output is correct
3 Correct 0 ms 2124 KB Output is correct
4 Correct 16 ms 2124 KB Output is correct
5 Correct 3 ms 2124 KB Output is correct
6 Correct 66 ms 2124 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 2124 KB Output is correct
2 Correct 199 ms 2124 KB Output is correct
3 Correct 286 ms 2124 KB Output is correct
4 Correct 143 ms 2124 KB Output is correct