Submission #597047

#TimeUsernameProblemLanguageResultExecution timeMemory
597047andrei_boacaThe Forest of Fangorn (CEOI14_fangorn)C++14
10 / 100
3050 ms468 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3") using namespace std; typedef long double ld; const ld EPS=1e-9; int n,c,w,h; struct point { ld 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) { ld a1=A.b.y-A.a.y; ld b1=A.a.x-A.b.x; ld c1=-a1*A.a.x-b1*A.a.y; ld a2=B.b.y-B.a.y; ld b2=B.a.x-B.b.x; ld 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); } ld x=(b1*c2-b2*c1)/(a1*b2-a2*b1); ld y=(-c2-a2*x)/b2; return {x,y}; } ld dist(point a, point b) { ld 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; ld 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) { if(!inmat(a)) return 0; ld d1=dist(L.a,L.b); ld d2=dist(L.a,a)+dist(a,L.b); return abs(d1-d2)<=EPS; } ld panta(line L) { ld a1=L.b.y-L.a.y; ld b1=L.a.x-L.b.x; ld c1=-a1*L.a.x-b1*L.a.y; if(b1==0) return 1e9; return (-a1)/b1; } bool issame(point a, point b) { return abs(a.x-b.x)<=EPS&&abs(a.y-b.y)<=EPS; } vector<line> plin,gol; point start; bool isbad(line L1,line L2) { point comun={-1,-1}; if(issame(L1.a,L2.a)) comun=L1.a; if(issame(L1.a,L2.b)) comun=L1.a; if(issame(L1.b,L2.a)) comun=L1.b; if(issame(L1.b,L2.b)) comun=L1.b; if(!inmat(comun)) return 0; if(issame(L1.a,comun)) swap(L1.a,L1.b); if(issame(L2.a,comun)) swap(L2.a,L2.b); line u={G,L1.a}; line t={G,L2.a}; point Ui=intersect(L2,u); point Ti=intersect(L1,t); bool isu=online(Ui,u); bool ist=online(Ti,t); if(isu!=ist) return 0; else return 1; } bool comp(point a, point b) { if(issame(a,start)) return 1; if(issame(b,start)) return 0; a.x-=start.x; a.y-=start.y; b.x-=start.x; b.y-=start.y; ld vala=0,valb=0; if(a.y==0) return 1; if(b.y==0) return 0; return a.x*b.y<a.y*b.x; } int main() { cin>>w>>h; cin>>G.x>>G.y; 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++) lines.push_back({tree[i],tree[j]});*/ for(int z=1;z<=c;z++) { /*plin.clear(); gol.clear(); for(auto l:lines) { line q={G,camps[z]}; point i=intersect(l,q); if(inmat(i)&&online(i,q)) gol.push_back(l); else plin.push_back(l); }*/ bool ok=1; /*for(int i=1;i<=n&&ok;i++) { vector<point> plin,gol; for(int j=1;j<=n&&ok;j++) if(j!=i) { line l={tree[i],tree[j]}; line q={G,camps[z]}; point P=intersect(l,q); if(inmat(P)&&online(P,q)) gol.push_back(tree[j]); else plin.push_back(tree[j]); } for(point a:plin) for(point b:gol) { line L1={tree[i],a}; line L2={tree[i],b}; line u={G,L2.a}; line t={G,L2.b}; point Ui=intersect(u,L1); point Ti=intersect(t,L1); if(inmat(Ui)&&inmat(Ti)) if(online(Ui,u)&&online(Ti,t)) { ok=0; break; } if(!ok) break; } }*/ for(int i=1;i<=n&&ok;i++) { vector<point> points; for(int j=1;j<=n;j++) if(j!=i) { line l={tree[i],tree[j]}; line q={G,camps[z]}; point P=intersect(l,q); if(inmat(P)&&online(P,q)) points.push_back(tree[j]); } start={1e9,1e9}; for(point j:points) { if(j.x<start.x) start=j; else if(j.x==start.x&&j.y==start.y) start=j; } sort(points.begin(),points.end(),comp); for(int j=1;j<points.size();j++) { line L1={tree[i],points[j]}; line L2={tree[i],points[j-1]}; if(isbad(L1,L2)) { ok=0; break; } } } if(ok) sol.push_back(z); } cout<<sol.size()<<'\n'; for(int i:sol) cout<<i<<' '; return 0; }

Compilation message (stderr)

fangorn.cpp: In function 'ld panta(line)':
fangorn.cpp:71:8: warning: unused variable 'c1' [-Wunused-variable]
   71 |     ld c1=-a1*L.a.x-b1*L.a.y;
      |        ^~
fangorn.cpp: In function 'bool comp(point, point)':
fangorn.cpp:120:8: warning: unused variable 'vala' [-Wunused-variable]
  120 |     ld vala=0,valb=0;
      |        ^~~~
fangorn.cpp:120:15: warning: unused variable 'valb' [-Wunused-variable]
  120 |     ld vala=0,valb=0;
      |               ^~~~
fangorn.cpp: In function 'int main()':
fangorn.cpp:208:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  208 |             for(int j=1;j<points.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...