Submission #110570

#	Time	Username	Problem	Language	Result	Execution time	Memory
110570		ckodser	The Forest of Fangorn (CEOI14_fangorn)	C++14	100 / 100	1531 ms	1152 KiB

fangorn

#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 / 30
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 20 / 20