Submission #596047

#TimeUsernameProblemLanguageResultExecution timeMemory
596047andrei_boacaThe Forest of Fangorn (CEOI14_fangorn)C++14
0 / 100
500 ms65536 KiB
#include <bits/stdc++.h> using namespace std; const double EPS=1e-9; int n,c,w,h; struct point { double x,y; } G,camps[10005],tree[10005]; struct line { point a,b; }; vector<line> lines; bool inmat(point p) { return p.x>=0&&p.x<=w&&p.y>=0&&p.y<=h; } point intersect(line A, line B) { double a1=A.b.y-A.a.y; double b1=A.a.x-A.b.x; double c1=-a1*A.a.x-b1*A.a.y; double a2=B.b.y-B.a.y; double b2=B.a.x-B.b.x; double c2=-a2*B.a.x-b2*B.a.y; if(a1==0&&a2==0) return {-1,-1}; if(b1==0&&b2==0) return {-1,-1}; if(b2==0) { swap(a1,a2); swap(b1,b2); swap(c1,c2); } double x=(b1*c2-b2*c1)/(a1*b2-a2*b1); double y=(-c2-a2*x)/b2; return {x,y}; } double dist(point a, point b) { double val=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); return sqrt(val); } vector<int> mylines,sol,Glines; bool conv=0; const double beams=180; const double PI=3.14159265359; double aria(point a, point b, point c) { a.x-=c.x; a.y-=c.y; b.x-=c.x; b.y-=c.y; return a.x*b.y-a.y*b.x; } bool online(point a, line L) { double d1=dist(L.a,L.b); double d2=dist(L.a,a)+dist(a,L.b); return abs(d1-d2)<=EPS; } bool prt=0; void laser(point p) { mylines.clear(); conv=1; double grade=0,rad=0; double ip=10.0; vector<bool> f; f.resize((int)lines.size()); vector<point> ups,downs,poli; while(grade<=beams) { double x=ip*cos(rad)+p.x; double y=ip*sin(rad)+p.y; point q={x,y}; point up={1e9,1e9},down={-1e9,-1e9}; int lup=-1,ldown=-1; line l={p,q}; for(int i=0;i<lines.size();i++) { point a=intersect(l,lines[i]); if(inmat(a)&&online(a,lines[i])) { if(a.y>=p.y+EPS&&a.y<up.y) { up=a; lup=i; } if(a.y<=p.y-EPS&&a.y>down.y) { down=a; ldown=i; } } } if(lup>=0&&f[lup]==0) { f[lup]=1; mylines.push_back(lup); ups.push_back(up); } if(ldown>=0&&f[ldown]==0) { f[ldown]=1; mylines.push_back(ldown); downs.push_back(down); } grade++; rad+=PI/beams; } reverse(downs.begin(),downs.end()); for(auto i:ups) poli.push_back(i); for(auto i:downs) poli.push_back(i); sort(mylines.begin(),mylines.end()); mylines.erase(unique(mylines.begin(),mylines.end()),mylines.end()); if(prt) { /*for(auto i:poli) cout<<i.x<<' '<<i.y<<'\n';*/ /*for(auto i:mylines) { line l=lines[i]; cout<<l.a.x<<' '<<l.a.y<<' '<<l.b.x<<' '<<l.b.y<<'\n'; } cout<<'\n';*/ } conv=1; for(int i=2;i<poli.size();i++) { point a=poli[i-2]; point b=poli[i-1]; point c=poli[i]; /*if(prt) cout<<aria(a,b,c)<<'\n';*/ if(aria(a,b,c)>0) { conv=0; break; } } } int main() { cin>>w>>h; cin>>G.x>>G.y; lines.push_back({{0,0},{0,h}}); lines.push_back({{0,0},{w,0}}); lines.push_back({{w,h},{0,h}}); lines.push_back({{w,h},{w,0}}); cin>>c; for(int i=1;i<=c;i++) cin>>camps[i].x>>camps[i].y; cin>>n; for(int i=1;i<=n;i++) cin>>tree[i].x>>tree[i].y; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) { line l={tree[i],tree[j]}; for(int p=0;p<4;p++) { point a=intersect(lines[p],l); if(inmat(a)) { double d=dist(tree[i],a)+dist(tree[i],tree[j]); double d2=dist(tree[j],a); if(abs(d-d2)<=EPS) lines.push_back({tree[i],a}); else lines.push_back({tree[j],a}); } } } laser(G); if(conv==0) mylines.clear(); else { Glines=mylines; sort(Glines.begin(),Glines.end()); Glines.erase(unique(Glines.begin(),Glines.end()),Glines.end()); } for(int i=1;i<=c;i++) { if(i==2) prt=1; else prt=0; laser(camps[i]); if(conv) { if(Glines.empty()) continue; sort(mylines.begin(),mylines.end()); mylines.erase(unique(mylines.begin(),mylines.end()),mylines.end()); if(mylines.size()==Glines.size()) { bool ok=1; for(int j=0;j<mylines.size();j++) if(mylines[j]!=Glines[j]) ok=0; if(ok) sol.push_back(i); } } else { if(Glines.empty()) sol.push_back(i); } } cout<<sol.size()<<'\n'; for(int i:sol) cout<<i<<' '; return 0; }

Compilation message (stderr)

fangorn.cpp: In function 'void laser(point)':
fangorn.cpp:84:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for(int i=0;i<lines.size();i++)
      |                     ~^~~~~~~~~~~~~
fangorn.cpp:135:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     for(int i=2;i<poli.size();i++)
      |                 ~^~~~~~~~~~~~
fangorn.cpp: In function 'int main()':
fangorn.cpp:153:31: warning: narrowing conversion of 'h' from 'int' to 'double' [-Wnarrowing]
  153 |     lines.push_back({{0,0},{0,h}});
      |                               ^
fangorn.cpp:154:29: warning: narrowing conversion of 'w' from 'int' to 'double' [-Wnarrowing]
  154 |     lines.push_back({{0,0},{w,0}});
      |                             ^
fangorn.cpp:155:23: warning: narrowing conversion of 'w' from 'int' to 'double' [-Wnarrowing]
  155 |     lines.push_back({{w,h},{0,h}});
      |                       ^
fangorn.cpp:155:25: warning: narrowing conversion of 'h' from 'int' to 'double' [-Wnarrowing]
  155 |     lines.push_back({{w,h},{0,h}});
      |                         ^
fangorn.cpp:155:31: warning: narrowing conversion of 'h' from 'int' to 'double' [-Wnarrowing]
  155 |     lines.push_back({{w,h},{0,h}});
      |                               ^
fangorn.cpp:156:23: warning: narrowing conversion of 'w' from 'int' to 'double' [-Wnarrowing]
  156 |     lines.push_back({{w,h},{w,0}});
      |                       ^
fangorn.cpp:156:25: warning: narrowing conversion of 'h' from 'int' to 'double' [-Wnarrowing]
  156 |     lines.push_back({{w,h},{w,0}});
      |                         ^
fangorn.cpp:156:29: warning: narrowing conversion of 'w' from 'int' to 'double' [-Wnarrowing]
  156 |     lines.push_back({{w,h},{w,0}});
      |                             ^
fangorn.cpp:206:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  206 |                 for(int j=0;j<mylines.size();j++)
      |                             ~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...