#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
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 time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Correct |
5 ms |
212 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 6 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
| 7 |
Incorrect |
90 ms |
596 KB |
Output isn't correct |
| 8 |
Incorrect |
84 ms |
596 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
392 KB |
Output isn't correct |
| 2 |
Incorrect |
51 ms |
468 KB |
Output isn't correct |
| 3 |
Correct |
113 ms |
596 KB |
Output is correct |
| 4 |
Incorrect |
134 ms |
596 KB |
Output isn't correct |
| 5 |
Incorrect |
136 ms |
596 KB |
Output isn't correct |
| 6 |
Incorrect |
396 ms |
1356 KB |
Output isn't correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
4 ms |
212 KB |
Output is correct |
| 9 |
Incorrect |
85 ms |
596 KB |
Output isn't correct |
| 10 |
Incorrect |
500 ms |
1484 KB |
Output isn't correct |
| 11 |
Correct |
439 ms |
2504 KB |
Output is correct |
| 12 |
Incorrect |
347 ms |
1484 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
93 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
