#include <bits/stdc++.h>
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
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 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 |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
2 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
212 KB |
Output is correct |
| 2 |
Correct |
3 ms |
212 KB |
Output is correct |
| 3 |
Correct |
15 ms |
328 KB |
Output is correct |
| 4 |
Correct |
7 ms |
340 KB |
Output is correct |
| 5 |
Correct |
5 ms |
340 KB |
Output is correct |
| 6 |
Correct |
13 ms |
344 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
4 ms |
212 KB |
Output is correct |
| 10 |
Correct |
23 ms |
320 KB |
Output is correct |
| 11 |
Correct |
33 ms |
332 KB |
Output is correct |
| 12 |
Correct |
34 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
3 ms |
212 KB |
Output is correct |
| 3 |
Correct |
3 ms |
212 KB |
Output is correct |
| 4 |
Correct |
438 ms |
416 KB |
Output is correct |
| 5 |
Correct |
140 ms |
360 KB |
Output is correct |
| 6 |
Correct |
2583 ms |
524 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3067 ms |
468 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
