Submission #113682

#TimeUsernameProblemLanguageResultExecution timeMemory
113682Adhyyan1252The Forest of Fangorn (CEOI14_fangorn)C++11
100 / 100
2743 ms1116 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long struct point{ ll x, y; int indx; point(){ x = 0, y = 0; indx = -10000; } point(ll X, ll Y, int Indx){ x = X; y = Y; indx = Indx; } point operator-(const point& other){ return point(x-other.x, y-other.y, indx); } point operator*(const int o){ return point(x*o, y*o, indx); } }; ll cross(const point& a, const point& b){ return (a.x*b.y - a.y*b.x); } bool comp(const point& a, const point& b){ if(a.y >= 0 && b.y < 0) return true; if(b.y >= 0 && a.y < 0) return false; return cross(a, b) > 0LL; } signed main(){ ios::sync_with_stdio(false); cin.tie(0); int w, h; cin>>w>>h; vector<point> camps(1); cin>>camps[0].x>>camps[0].y; camps[0].indx = 0; int c; cin>>c; camps.resize(c+1); for(int i = 1; i <= c; i++){ cin>>camps[i].x>>camps[i].y; camps[i].indx = i; } int n; cin>>n; vector<point> points(n); for(int i = 0; i < n; i++){ cin>>points[i].x>>points[i].y; points[i].indx = i; } bitset<10005> R; R.flip(); for(int i = 0; i < n; i++){ //cout<<"DOING POint"<<i<<endl; //considering point i as center vector<point> p; p.reserve(n+camps.size()); for(int j = 0; j < n; j++){ if(i == j) continue; p.push_back((points[i]-points[j])); p.back().indx = j; } for(int j = 0; j < camps.size(); j++){ p.push_back(camps[j]-points[i]); p.back().indx = p.back().indx*-1 - 1; } sort(p.begin(), p.end(), comp); // for(int i = 0; i < p.size(); i++) cout<<"("<<p[i].indx<<", "<<p[i].x<<", "<<p[i].y<<" )"; // cout<<endl; bitset<10005> reach; int indx = -1; for(indx = 0; indx < p.size(); indx++){ if(p[indx].indx == -1) break; } reach[0] = true; assert(indx != -1 && indx != p.size()); for(int i = (indx-1+p.size())%p.size(); i != indx; i = (i - 1 + p.size())%p.size()){ if(p[i].indx >= 0 || reach[p[i].indx*-1-1]) break; reach[p[i].indx*-1 - 1] = true; } for(int i = (indx+1)%p.size(); i != indx; i = (i + 1)%p.size()){ if(p[i].indx >= 0 || reach[p[i].indx*-1-1]) break; reach[p[i].indx*-1 - 1] = true; } //cout<<"LOLOL"<<endl; R &= reach; } assert(R[0]); vector<int> ans; for(int i = 1; i <= c; i++) if(R[i]) ans.push_back(i); cout<<ans.size()<<endl; for(int a: ans){ cout<<a<<" "; } cout<<endl; }

Compilation message (stderr)

fangorn.cpp: In function 'int main()':
fangorn.cpp:59:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < camps.size(); j++){
                  ~~^~~~~~~~~~~~~~
fangorn.cpp:68:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(indx = 0; indx < p.size(); indx++){
                 ~~~~~^~~~~~~~~~
In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from fangorn.cpp:1:
fangorn.cpp:72:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   assert(indx != -1 && indx != p.size());
                        ~~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...