oj.uz

Submission #110570

# Submission time Handle Problem Language Result Execution time Memory
110570 2019-05-11T08:10:06 Z ckodser The Forest of Fangorn (CEOI14_fangorn) C++14
100 / 100
 1531 ms 1152 KB 
#include<bits/stdc++.h>

#define ll int
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll> 
#define point complex<ld> 
#define X real
#define Y imag
using namespace :: std;

const ll mod=1e9+7;
const ll maxn=1e5+500;
const ll inf=1e9+900;
const ld PI2=atan2(0,-1)*2;
const ld PI=atan2(0,-1);

ld ok(ld a){
    if(a<0)return a+PI2;
    return a;
}
ld ok2(ld a){
    if(a>PI)return a-PI2;
    return a;
}
point getpoint(){
    ll x,y;
    cin>>x>>y;
    point e;
    e.X(x);
    e.Y(y);
    return e;
}
void pri(vector<ll> ans){
    cout<<ans.size()<<endl;
    for(auto e:ans){
	cout<<e+1<<' ';
    }
}


point camp[maxn];
point tree[maxn];
ld dl[maxn];
ld dt[maxn];

bool is_bad(point a,ll n){
    for(ll j=0;j<n;j++){
	ld r=ok(arg(a-tree[j])-dl[j]);
	if(r<=dt[j]){
	    return 1;
	}
    }
    return 0;
}

ld tmp[maxn];
ll cnttmp;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll n,c,w,h;
    cin>>w>>h;

    point g=getpoint();
    cin>>c;
    for(ll i=0;i<c;i++){
	camp[i]=getpoint();	
    }
    cin>>n;
    for(ll i=0;i<n;i++){
	tree[i]=getpoint();
    }
    for(ll i=0;i<n;i++){
	cnttmp=0;
	for(ll j=0;j<n;j++){
	    if(j!=i){
		tmp[cnttmp]=arg(tree[i]-tree[j]);
		cnttmp++;
	    }
	}
	ld r=arg(g-tree[i]);
	ld minn=inf;
	ld maxx=0;
	for(ll j=0;j<cnttmp;j++){
	    ld e=tmp[j];
	    ld w=ok(e-r);
	    minn=min(minn,w);
	    maxx=max(maxx,w);
	}
	dl[i]=ok2(r+minn);
	dt[i]=ok(maxx-minn);
    }
    vector<ll> ans;
    for(ll i=0;i<c;i++){
	if(!is_bad(camp[i],n)){
	    ans.pb(i);
	}	
    }
    pri(ans);
    
}

Subtask #1
30.0 / 30.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 82 ms 504 KB Output is correct
5 Correct 20 ms 384 KB Output is correct
6 Correct 312 ms 760 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 500 ms 744 KB Output is correct
2 Correct 1531 ms 1028 KB Output is correct
3 Correct 339 ms 1152 KB Output is correct
4 Correct 1110 ms 1148 KB Output is correct