oj.uz

Submission #110569

# Submission time Handle Problem Language Result Execution time Memory
110569 2019-05-11T08:07:58 Z ckodser The Forest of Fangorn (CEOI14_fangorn) C++14
30 / 100
 664 ms 1272 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;
    
    /*
    for(ll i=-1;i<=1;i++){
	for(ll j=-1;j<=1;j++){
	    point e;
	    e.X(i);
	    e.Y(j);
	    cout<<i<<" "<<j<<":"<<arg(e)<<endl;
	}
    }*/


    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<n;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 400 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
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Incorrect 3 ms 384 KB Output isn't correct
3 Incorrect 3 ms 356 KB Output isn't correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 5 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 3 ms 384 KB Output is correct
10 Correct 7 ms 384 KB Output is correct
11 Incorrect 10 ms 384 KB Output isn't correct
12 Incorrect 9 ms 384 KB Output isn't correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 84 ms 504 KB Output is correct
5 Correct 22 ms 512 KB Output is correct
6 Incorrect 664 ms 776 KB Output isn't correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 744 KB Output is correct
2 Incorrect 585 ms 1272 KB Output isn't correct
3 Halted 0 ms 0 KB -