Submission #377880

#TimeUsernameProblemLanguageResultExecution timeMemory
377880UtahaThe Forest of Fangorn (CEOI14_fangorn)C++14
50 / 100
3057 ms492 KiB
/*input 9 4 1 2 1 8 4 4 1 1 6 1 3 3 4 3 */ #include <bits/stdc++.h> #pragma GCC optimize("unroll-loops,no-stack-protector") using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<ld,ld> pdd; #define IOS ios_base::sync_with_stdio(0); cin.tie(0) #define ALL(a) a.begin(),a.end() #define SZ(a) ((int)a.size()) #define F first #define S second #define REP(i,n) for(int i=0;i<((int)n);i++) #define eb emplace_back #define pb push_back #define MP(a,b) make_pair(a,b) #define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end())))) #define GET_POS(c,x) (int)(lower_bound(c.begin(),c.end(),x)-c.begin()) #define EL cout<<'\n' #define BS(a,x) binary_search(ALL(a),x) template<typename T1,typename T2> ostream& operator<<(ostream& out,pair<T1,T2> P){ out<<'('<<P.F<<','<<P.S<<')'; return out; } template<typename T> ostream& operator<<(ostream& out,vector<T> V){ REP(i,SZ(V)) out<<V[i]<<((i!=SZ(V)-1)?" ":""); return out; } //}}} const ll maxn=10005; const ll maxlg=20; const ll INF64=1e18; const int INF=0x3f3f3f3f; const ll MOD=ll(1e9+7); const ld PI=acos(-1); const ld eps=1e-9; //const ll p=880301; //const ll P=31; ll mypow(ll a,ll b){ ll res=1LL; while(b){ if(b&1) res=res*a%MOD; a=a*a%MOD; b>>=1; } return res; } pii operator - (pii A, pii B){ return MP(A.F-B.F, A.S-B.S); } ll cross(pii A, pii B){ return (ll)A.F * B.S - (ll) A.S * B.F > 0; } int n,C; int Ex[maxn],Ey[maxn]; int X[maxn],Y[maxn]; bool cmp(pair<pii,int> A, pair<pii,int> B){ return atan2(A.F.F, A.F.S) < atan2(B.F.F, B.F.S); } vector<int> getOrder(int x, int y){ vector<pair<pii,int>> v; REP(i,n) v.eb(MP(X[i]-x, Y[i]-y), i); sort(ALL(v), cmp); int idx = -1; REP(i,n) if(v[i].S == 0) idx = i; vector<int> res; for(int i=idx; i<n; i++) res.pb(v[i].S); REP(i,idx) res.pb(v[i].S); return res; } bool check(pii A, pii B, pii _C){ const pii O = MP(0, 0); if(cross(A, B) != cross(B, _C)) return 0; if(cross(_C-A, B-A) != cross(B-A, O-A)) return 0; if(cross(A-_C, B-_C) != cross(B-_C, O-_C)) return 0; return 1; } int main(){ IOS; int h, w; int Sx, Sy; cin>>h>>w>>Sx>>Sy; cin>>C; REP(i,C){ cin>>Ex[i]>>Ey[i]; } cin>>n; REP(i,n){ cin>>X[i]>>Y[i]; } vector<int> ans; const vector<int> tmp = getOrder(Sx, Sy); REP(i,C){ // cout<<getOrder(Ex[i], Ey[i])<<'\n'; if(getOrder(Ex[i], Ey[i]) != tmp) continue; bool f = 1; REP(j,n) REP(k,n) REP(l,n){ if(j == k or k == l or j == l) continue; if(check(MP(X[j], Y[j]) - MP(Sx, Sy), MP(X[k], Y[k]) - MP(Sx, Sy), MP(X[l], Y[l]) - MP(Sx, Sy))){ if(!check(MP(X[j], Y[j]) - MP(Ex[i], Ey[i]), MP(X[k], Y[k]) - MP(Ex[i], Ey[i]), MP(X[l], Y[l]) - MP(Ex[i], Ey[i]))){ f = 0; } } } if(f) ans.pb(i); } cout<<SZ(ans)<<'\n'; REP(i, SZ(ans)){ cout<<ans[i] + 1<<" \n"[i==SZ(ans)-1]; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...