added working NWERC11C
[the-user-spoj:the-user-spoj.git] / NWERC11I.cpp
1 #include <cstdio>
2 #include <set>
3 #include <cmath>
4 #include <iostream>
5 #include <algorithm>
6 #include <vector>
7 using namespace std;
8
9 typedef long long int INT;
10
11 template<typename T>
12 inline T sqr(const T& x)
13 {
14     return x * x;
15 }
16
17 struct point
18 {
19     INT x, y;
20     point()
21     {}
22     point(const point& o) : x(o.x), y(o.y)
23     {}
24     point(INT x, INT y) : x(x), y(y)
25     {}
26     inline INT operator*(const point& o) const
27     {
28         return x*o.x + y*o.y;
29     }
30     inline point operator+(const point& o) const
31     {
32         return point(x+o.x, y+o.y);
33     }
34     inline point operator-(const point& o) const
35     {
36         return point(x-o.x, y-o.y);
37     }
38     inline bool operator==(const point& o) const
39     {
40         return x == o.x && y == o.y;
41     }
42 };
43
44 inline bool xfirst(const point& a, const point& b)
45 {
46     return a.x < b.x || (a.x == b.x && a.y < b.y);
47 }
48
49 inline bool yfirst(const point& a, const point& b)
50 {
51     return a.y < b.y || (a.y == b.y && a.x < b.x);
52 }
53
54 inline bool xfirstWithID(const pair<point, INT>& a, const pair<point, INT>& b)
55 {
56     return xfirst(a.first, b.first) || (a.first == b.first && a.second < b.second);
57 }
58
59 inline bool yfirstWithID(const pair<point, INT>& a, const pair<point, INT>& b)
60 {
61     return yfirst(a.first, b.first) || (a.first == b.first && a.second < b.second);
62 }
63
64 inline double norm(const point& p)
65 {
66     return sqrt(double(p*p));
67 }
68
69 inline INT dist2(const point& a, const point& b)
70 {
71     return (a-b)*(a-b);
72 }
73
74 typedef pair<point, point> lineseg;
75
76 inline double angle(const point& x, const point& y, const point& z)
77 {
78     return acos(double((z-y)*(x-y))/norm(z-y)/norm(x-y));
79 }
80
81 inline bool intersect(lineseg s1, lineseg s2)
82 {
83     static const double _2PI = 4*acos(0.0) - 0.000001; // with tolerance
84     return angle(s1.first, s2.first, s1.second)
85          + angle(s1.first, s2.second, s1.second)
86          + angle(s2.first, s1.first, s2.second)
87          + angle(s2.first, s1.second, s2.second) >= _2PI;
88 }
89
90 int main()
91 {
92 //     cerr << intersect(make_pair(point(0,0), point(1,1)), make_pair(point(0,1), point(1,0))) << endl;
93 //     cerr << intersect(make_pair(point(-4, -1), point(5, -1)), make_pair(point(0, 0), point(0,-2))) << endl;
94 //     cerr << intersect(make_pair(point(0,-10), point(0,0)), make_pair(point(0,-2),point(0,-8))) << endl;
95     INT _t = 0;
96     scanf("%lld", &_t);
97     for(INT _i = 0; _i != _t; ++_i)
98     {
99         INT s, r, w, p;
100         scanf("%lld %lld %lld %lld", &s, &r, &w, &p);
101         vector<pair<point, INT> > products(p);
102         vector<point> sensors(s);
103         vector<lineseg> walls(w);
104         for(INT i = 0; i != s; ++i)
105             scanf("%lld %lld", &sensors[i].x, &sensors[i].y);
106         for(INT i = 0; i != w; ++i)
107             scanf("%lld %lld %lld %lld", &walls[i].first.x, &walls[i].first.y, &walls[i].second.x, &walls[i].second.y);
108         for(INT i = 0; i != p; ++i)
109         {
110             products[i].second = i;
111             scanf("%lld %lld", &products[i].first.x, &products[i].first.y);
112         }
113         
114         sort(products.begin(), products.end(), xfirstWithID);
115         sort(sensors.begin(), sensors.end(), xfirst);
116         
117         vector<vector<INT> > result(p);
118         
119         set<pair<point, INT>, typeof(&yfirstWithID)> status(&yfirstWithID);
120         
121         INT inprod = 0, outprod = 0, query = 0;
122         
123         while(outprod != p && query != s)
124         {
125             point& nextin = products[inprod == p ? 0 : inprod].first;
126             point& nextout = products[outprod].first;
127             point& nextquery = sensors[query];
128             if(inprod != p && nextin.x - r <= nextquery.x && nextin.x - r <= nextout.x+r)
129             {
130                 status.insert(products[inprod]);
131                 ++inprod;
132             }
133             else if(nextquery.x <= nextout.x + r)
134             {
135                 pair<point, INT> lo = make_pair(point(-1000000000, nextquery.y - r), -1000000000), hi = make_pair(point(1000000000, nextquery.y + r), 1000000000);
136 //                 for(typeof(status.begin()) i = status.begin(); i != status.end(); ++i)
137 //                 {
138 //                     cerr << " (" << i->first.x << "," << i->first.y << ")";
139 //                 }
140 //                 cerr << endl;
141                 typeof(status.begin()) beg = status.lower_bound(lo), end = status.upper_bound(hi);
142                 for(typeof(status.begin()) i = beg; i != end; ++i)
143                 {
144 //                     cerr << "c" << " (" << nextquery.x << "," << nextquery.y << ") (" << i->first.x << "," << i->first.y << ")" << endl;
145                     if(dist2(nextquery, i->first) <= sqr(r))
146                     {
147                         INT realr = r;
148                         for(INT j = 0; j != w; ++j)
149                             if(intersect(walls[j], make_pair(nextquery, i->first)))
150                                 --realr;
151                         if(realr >= 0 && dist2(nextquery, i->first) <= sqr(realr))
152                         {
153 //                             cerr << realr << " (" << nextquery.x << "," << nextquery.y << ") (" << i->first.x << "," << i->first.y << endl;
154                             result[i->second].push_back(query);
155                         }
156                     }
157                 }
158                 ++query;
159             }
160             else
161             {
162                 status.erase(products[outprod]);
163                 ++outprod;
164             }
165         }
166         
167         for(INT i = 0; i != p; ++i)
168         {
169             printf("%lu", result[i].size());
170             for(size_t j = 0; j != result[i].size(); ++j)
171                 printf(" (%lld,%lld)", sensors[result[i][j]].x, sensors[result[i][j]].y);
172             printf("\n");
173         }
174     }
175 }