#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
mt19937_64 rng(chrono::steady_clock().now().time_since_epoch().count());
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 {-1e9,-1e9};
if(b1==0&&b2==0)
return {-1e9,-1e9};
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;
const ld beams=360;
const ld PI=3.14159265359;
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;
const int lim=100;
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);
}
shuffle(plin.begin(),plin.end(),rng);
shuffle(gol.begin(),gol.end(),rng);
bool ok=1;
int cnt1=0;
int cnt2=0;
for(auto L1:plin)
{
cnt1++;
cnt2=0;
if(cnt1>lim)
break;
for(auto L2:gol)
{
cnt2++;
if(cnt2>lim)
break;
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;
}
cnt1=0,cnt2=0;
for(int i=0;i<gol.size()&&ok&&cnt1<=lim;i++,cnt1++)
for(int j=i+1;j<gol.size()&&ok&&cnt2<=lim;j++,cnt2++)
{
line L1=gol[i];
line L2=gol[j];
point comun=intersect(L1,L2);
if(comun.x==-1e9&&comun.y==-1e9)
continue;
vector<int> vals;
if(!issame(L1.a,comun))
{
line u={G,L1.a};
point Ui=intersect(u,L2);
if(online(Ui,u))
vals.push_back(1);
else
vals.push_back(0);
}
if(!issame(L1.b,comun))
{
line u={G,L1.b};
point Ui=intersect(u,L2);
if(online(Ui,u))
vals.push_back(1);
else
vals.push_back(0);
}
if(!issame(L2.a,comun))
{
line u={G,L2.a};
point Ui=intersect(u,L1);
if(online(Ui,u))
vals.push_back(1);
else
vals.push_back(0);
}
if(!issame(L2.b,comun))
{
line u={G,L2.b};
point Ui=intersect(u,L1);
if(online(Ui,u))
vals.push_back(1);
else
vals.push_back(0);
}
bool all=1;
for(int i:vals)
if(i!=vals[0])
all=0;
if(all)
ok=0;
}
if(ok)
sol.push_back(z);
}
cout<<sol.size()<<'\n';
for(int i:sol)
cout<<i<<' ';
return 0;
}
Compilation message
fangorn.cpp: In function 'ld panta(line)':
fangorn.cpp:74:8: warning: unused variable 'c1' [-Wunused-variable]
74 | ld c1=-a1*L.a.x-b1*L.a.y;
| ^~
fangorn.cpp: In function 'int main()':
fangorn.cpp:142:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | for(int i=0;i<gol.size()&&ok&&cnt1<=lim;i++,cnt1++)
| ~^~~~~~~~~~~
fangorn.cpp:143:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
143 | for(int j=i+1;j<gol.size()&&ok&&cnt2<=lim;j++,cnt2++)
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
2 ms |
976 KB |
Output is correct |
| 8 |
Correct |
4 ms |
992 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
432 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
468 KB |
Output isn't correct |
| 3 |
Correct |
5 ms |
848 KB |
Output is correct |
| 4 |
Correct |
3 ms |
912 KB |
Output is correct |
| 5 |
Correct |
2 ms |
912 KB |
Output is correct |
| 6 |
Incorrect |
7 ms |
2120 KB |
Output isn't correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
3 ms |
848 KB |
Output is correct |
| 10 |
Correct |
15 ms |
5476 KB |
Output is correct |
| 11 |
Correct |
14 ms |
4548 KB |
Output is correct |
| 12 |
Incorrect |
18 ms |
4548 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
3 ms |
468 KB |
Output is correct |
| 3 |
Correct |
2 ms |
468 KB |
Output is correct |
| 4 |
Runtime error |
58 ms |
65536 KB |
Execution killed with signal 9 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
50 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
