Submission #448674

#TimeUsernameProblemLanguageResultExecution timeMemory
448674vanicThe Forest of Fangorn (CEOI14_fangorn)C++14
100 / 100
667 ms1196 KiB
#include <cstdio> #include <cmath> #include <algorithm> #include <vector> using namespace std; const int maxn=2005, maxm=1e4+5; const double inf=2e18; pair < int, int > d[maxn]; pair < int, int > q[maxm]; int n, m; vector < double > kor[4]; // jednadzbe: x=0, y=0, x=w, y=h vector < pair < double, int > > sw[4]; bool moze[maxm]; vector < int > sol; pair < int, int > pos; int w, h; void radi(int x, int y){ double a, b, c; int dx, dy; dx=d[x].first-d[y].first; dy=d[x].second-d[y].second; a=-dy; b=dx; c=-a*d[x].first-b*d[x].second; double sol1, sol2, sol3, sol4; if(b==0){ sol1=-inf; sol3=inf; } else{ sol1=-c/b; sol3=(-c-a*w)/b; } if(a==0){ sol2=-inf; sol4=inf; } else{ sol2=-c/a; sol4=(-c-b*h)/a; } if(b==0){ if(d[x].second<d[y].second){ kor[0].push_back(sol1); kor[2].push_back(sol1); } else{ kor[0].push_back(sol3); kor[2].push_back(sol3); } } else if(d[x].first<d[y].first){ kor[0].push_back(sol1); } else{ kor[2].push_back(sol3); } if(a==0){ if(d[x].first<d[y].first){ kor[1].push_back(sol2); kor[3].push_back(sol2); } else{ kor[1].push_back(sol4); kor[3].push_back(sol4); } } else if(d[x].second<d[y].second){ kor[1].push_back(sol2); } else{ kor[3].push_back(sol4); } } double ccw(pair < double, double > a, pair < double, double > b, pair < double, double > c){ return a.first*(b.second-c.second)+b.first*(c.second-a.second)+c.first*(a.second-b.second); } bool provjeri(pair < double, double > a, pair < double, double > b, pair < double, double > c, pair < double, double > x){ if(ccw(a, b, c)<0){ swap(b, c); } return ccw(a, b, x)>=0 && ccw(b, c, x)>=0 && ccw(c, a, x)>=0; } void rijesi(int x, int y){ sort(kor[y].begin(), kor[y].end()); pair < double, double > t1, t2; if(y==0){ t1.first=0; t2.first=0; } else if(y==1){ t1.second=0; t2.second=0; } else if(y==2){ t1.first=w; t2.first=w; } else{ t1.second=h; t2.second=h; } int ind=-1; for(int i=0; i<(int)kor[y].size()-1; i++){ if(y==0){ t1.second=kor[y][i]; t2.second=kor[y][i+1]; } else if(y==1){ t1.first=kor[y][i]; t2.first=kor[y][i+1]; } else if(y==2){ t1.second=kor[y][i]; t2.second=kor[y][i+1]; } else{ t1.first=kor[y][i]; t2.first=kor[y][i+1]; } if(provjeri(t1, t2, d[x], pos)){ ind=i; break; } } if(kor[y].size()>1){ sw[y].push_back({kor[y][0], 1}); sw[y].push_back({kor[y].back(), -1}); if(ind!=-1){ for(int i=0; i<m; i++){ if(moze[i] && !provjeri(t1, t2, d[x], q[i])){ moze[i]=0; } } sw[y].push_back({kor[y][ind], -1}); sw[y].push_back({kor[y][ind+1], 1}); } } } int main(){ scanf("%d%d", &w, &h); scanf("%d%d", &pos.first, &pos.second); scanf("%d", &m); for(int i=0; i<m; i++){ moze[i]=1; scanf("%d%d", &q[i].first, &q[i].second); } scanf("%d", &n); for(int i=0; i<n; i++){ scanf("%d%d", &d[i].first, &d[i].second); } for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ if(i==j){ continue; } radi(i, j); } for(int j=0; j<4; j++){ rijesi(i, j); kor[j].clear(); } } for(int i=0; i<m; i++){ if(q[i].first==0){ sw[0].push_back({q[i].second, i+2}); } else if(q[i].second==0){ sw[1].push_back({q[i].first, i+2}); } else if(q[i].first==w){ sw[2].push_back({q[i].second, i+2}); } else{ sw[3].push_back({q[i].first, i+2}); } } int val; for(int i=0; i<4; i++){ sort(sw[i].begin(), sw[i].end()); val=0; for(int j=0; j<(int)sw[i].size(); j++){ if(sw[i][j].second<2){ val+=sw[i][j].second; } else{ if(val || !moze[sw[i][j].second-2]){ continue; } sol.push_back(sw[i][j].second-1); } } } printf("%d\n", (int)sol.size()); sort(sol.begin(), sol.end()); for(int i=0; i<(int)sol.size(); i++){ printf("%d ", sol[i]); } printf("\n"); return 0; }

Compilation message (stderr)

fangorn.cpp: In function 'int main()':
fangorn.cpp:150:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |  scanf("%d%d", &w, &h);
      |  ~~~~~^~~~~~~~~~~~~~~~
fangorn.cpp:151:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |  scanf("%d%d", &pos.first, &pos.second);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:152:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |  scanf("%d", &m);
      |  ~~~~~^~~~~~~~~~
fangorn.cpp:155:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |   scanf("%d%d", &q[i].first, &q[i].second);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:157:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
fangorn.cpp:159:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |   scanf("%d%d", &d[i].first, &d[i].second);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...