#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const double EPS = 1e-8;
template <class T>
struct Point {
typedef Point P;
T x, y;
explicit Point(T x=0, T y=0) : x(x), y(y) {}
bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
P operator+(P p) const { return P(x+p.x, y+p.y); }
P operator-(P p) const { return P(x-p.x, y-p.y); }
P operator*(T d) const { return P(x*d, y*d); }
P operator/(T d) const { return P(x/d, y/d); }
T dot(P p) const { return x*p.x + y*p.y; }
T cross(P p) const { return x*p.y - y*p.x; }
T cross(P a, P b) const { return (a-*this).cross(b-*this); }
T dist2() const { return x*x + y*y; }
double dist() const { return sqrt((double)dist2()); }
// angle to x-axis in interval [-pi, pi]
double angle() const { return atan2(y, x); }
P unit() const { return *this/dist(); } // makes dist()=1
P perp() const { return P(-y, x); } // rotates +90 degrees
P normal() const { return perp().unit(); }
// returns point rotated 'a' radians ccw around the origin
P rotate(double a) const {
return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
};
template <class P>
int lineIntersection(const P& s1, const P& e1, const P& s2,
const P& e2, P& r) {
if ((e1-s1).cross(e2-s2)) { //if not parallell
r = s2-(e2-s2)*(e1-s1).cross(s2-s1)/(e1-s1).cross(e2-s2);
return 1;
} else
return -((e1-s1).cross(s2-s1)==0 || s2==e2);
}
int main(){
LL w, h;
cin >> w >> h;
Point<double> start_point;
cin >> start_point.x >> start_point.y;
int c;
cin >> c;
vector<Point<double> > camps(c);
for(int i = 0; i < c; i++){
cin >> camps[i].x >> camps[i].y;
}
int n;
cin >> n;
vector<Point<double> > trees(n);
for(int i = 0; i < n; i++){
cin >> trees[i].x >> trees[i].y;
}
vector<Point<double> > ray_start, ray_end;
for(int i = 0; i < n; i++){
// biggest, smallest angle();
int idx_min = -1;
double angle_min;
int idx_max = -1;
double angle_max;
for(int j = 0; j < n; j++){
if(i == j) continue;
Point<double> diff_dir = trees[j] - trees[i];
Point<double> base_dir = start_point - trees[i];
double delta = Point<double>(1,0).rotate(diff_dir.angle() - base_dir.angle()).angle();
if(idx_min == -1 || delta < angle_min){
idx_min = j;
angle_min = delta;
}
if(idx_max == -1 || delta > angle_max){
idx_max = j;
angle_max = delta;
}
}
ray_start.push_back(trees[i]);
ray_end.push_back(trees[i] * 2 - trees[idx_min]);
ray_start.push_back(trees[i]);
ray_end.push_back(trees[i] * 2 - trees[idx_max]);
}
vector<int> ans;
for(int i = 0; i < camps.size(); i++){
int ok = 1;
// check to see if these are okay
for(int a = 0; a < ray_start.size(); a++){
for(int b = 0; b < ray_start.size(); b++){
if(a == b) continue;
Point<double> s1 = ray_start[a];
Point<double> e1 = ray_end[a];
Point<double> s2 = ray_start[b];
Point<double> e2 = ray_end[b];
Point<double> r;
if(lineIntersection(s1, e1, s2, e2, r) != 1) continue;
if((r-s1).dot(e1-s1) < -EPS || (r-s2).dot(e2-s2) < -EPS) continue;
Point<double> sep1 = e1 - s1;
Point<double> sep2 = e2 - s2;
Point<double> ang1 = start_point - r;
Point<double> ang2 = camps[i] - r;
vector<pair<double, int> > f =
{{sep1.angle(), 0}, {sep2.angle(), 0},
{ang1.angle(), 1}, {ang2.angle(), 1}};
sort(f.begin(), f.end());
if(f[0].second == f[2].second){
ok = 0;
}
}
}
if(ok) ans.push_back(i);
}
cout << ans.size() << '\n';
for(int x : ans){
cout << x + 1 << ' ';
}
cout << endl;
}
Compilation message
fangorn.cpp: In function 'int main()':
fangorn.cpp:87:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < camps.size(); i++){
~~^~~~~~~~~~~~~~
fangorn.cpp:90:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int a = 0; a < ray_start.size(); a++){
~~^~~~~~~~~~~~~~~~~~
fangorn.cpp:91:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int b = 0; b < ray_start.size(); b++){
~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
504 KB |
Output is correct |
| 2 |
Correct |
3 ms |
504 KB |
Output is correct |
| 3 |
Correct |
3 ms |
556 KB |
Output is correct |
| 4 |
Correct |
3 ms |
556 KB |
Output is correct |
| 5 |
Correct |
2 ms |
556 KB |
Output is correct |
| 6 |
Correct |
3 ms |
556 KB |
Output is correct |
| 7 |
Correct |
13 ms |
564 KB |
Output is correct |
| 8 |
Correct |
10 ms |
588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
588 KB |
Output is correct |
| 2 |
Correct |
8 ms |
596 KB |
Output is correct |
| 3 |
Correct |
13 ms |
608 KB |
Output is correct |
| 4 |
Correct |
15 ms |
608 KB |
Output is correct |
| 5 |
Correct |
17 ms |
664 KB |
Output is correct |
| 6 |
Correct |
37 ms |
804 KB |
Output is correct |
| 7 |
Correct |
3 ms |
804 KB |
Output is correct |
| 8 |
Correct |
3 ms |
804 KB |
Output is correct |
| 9 |
Correct |
15 ms |
804 KB |
Output is correct |
| 10 |
Correct |
60 ms |
804 KB |
Output is correct |
| 11 |
Correct |
63 ms |
804 KB |
Output is correct |
| 12 |
Correct |
69 ms |
804 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
804 KB |
Output is correct |
| 2 |
Correct |
6 ms |
804 KB |
Output is correct |
| 3 |
Correct |
5 ms |
804 KB |
Output is correct |
| 4 |
Correct |
2556 ms |
864 KB |
Output is correct |
| 5 |
Correct |
385 ms |
864 KB |
Output is correct |
| 6 |
Execution timed out |
3046 ms |
1144 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3031 ms |
1220 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
