多校第9场第3题，一场比赛3个计算几何，甘版下风。
讲道理，看到题就知道是要转一圈，题目也规定了线段之间无相交，这也意味着以同一个点为中心，线段之间的遮挡关系是不变的，我们就可以通过维护当前角度上最近的线段，来判断某个点是否能被击中。
维护遮挡关系，可以直接比较他们与当前角度的射线的交点，到原点的距离，这里用了一些奇怪的方法来获得这个距离（这个方法只有在确定与射线有交点后才是正确的。
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<queue>
#include<set>
#include<ctime>
#include<map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ld eps = 1e-20;
ld PI = acos((ld)-1.0);
//#define ENABLE_FREAD
struct io_s {
bool negative;
char ch;
inline bool isdigitx(char c) {
return c >= '0' && c <= '9';
}
#ifdef ENABLE_FREAD
inline char nextchar() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
#else
inline char nextchar() {
return getchar();
}
#endif
template<typename T>
bool rn(T& _v) {
negative = false;
_v = 0;
while (!isdigitx(ch = nextchar()) && ch != EOF) { negative = ch == '-'; };
if (ch == EOF)return false;
do {
_v *= 10;
_v += ch - '0';
} while (isdigitx(ch = nextchar()));
if (negative) _v = -_v;
return true;
}
template<typename T>
bool run(T& _v) {
_v = 0;
while (!isdigitx(ch = nextchar()) && ch != EOF) {};
if (ch == EOF)return false;
do {
_v *= 10;
_v += ch - '0';
} while (isdigitx(ch = nextchar()));
return true;
}
template<typename T>
inline T r() {
T v = T();
rn(v);
return v;
}
inline int ri() { return r<int>(); }
inline ll rll() { return r<ll>(); }
inline int gets(char* s) {
return gets(s, ' ');
/*
char* c = s;
do {
ch = nextchar();
} while (ch == '
' || ch == '
');
do {
*(c++) = ch;
ch = nextchar();
} while (ch != '
' && ch != '
');
*(c++) = ' ';
return c - s - 1;
*/
}
inline int gets(char* s, char base) {
char* c = s;
do {
ch = nextchar();
} while (ch == '
' || ch == '
');
do {
*(c++) = ch - base;
ch = nextchar();
} while (ch != '
' && ch != '
');
*(c++) = ' ';
return c - s - 1;
}
inline char get() {
do {
ch = nextchar();
} while (ch <'A' || ch >'Z');
return ch;
}
template<class T>
inline void o(T p) {
static int stk[70], tp;
if (p == 0) { putchar('0'); return; }
if (p < 0) { p = -p; putchar('-'); }
while (p) stk[++tp] = p % 10, p /= 10;
while (tp) putchar(stk[tp--] + '0');
}
inline void ln() { putchar('
'); }
inline void space() { putchar(' '); }
template<class T>
inline void oln(T p) {
o(p); ln();
}
} io;
int n, m, q;
struct V2D {
ll x, y;
V2D() : x(0), y(0) {}
V2D(ll _x, ll _y) : x(_x), y(_y) {}
inline double acos() const {
return atan2(y, x);
}
inline ll len2() const {
return x*x + y*y;
}
inline ld len() const {
return sqrt(len2());
}
inline V2D operator *(const ll q) const {
return V2D(x*q, y*q);
}
inline ll operator ^(const V2D q) const {
return x*q.y - y*q.x;
}
inline ll operator *(const V2D q) const {
return x*q.x + y*q.y;
}
inline V2D operator +(const V2D q)const {
return V2D(x + q.x, y + q.y);
}
inline V2D operator -(const V2D q)const {
return V2D(x - q.x, y - q.y);
}
inline V2D operator +=(const V2D q) {
x += q.x, y += q.y;
return *this;
}
inline V2D operator -=(const V2D q) {
x -= q.x, y -= q.y;
return *this;
}
inline void read() {
io.rn(x), io.rn(y);
}
};
const int N = 1e4 + 10;
const int M = N * 3;
const int Q = 12 + 3;
V2D Enemies[N];
struct Wall {
V2D a, b;
} Walls[N];
bool ap[N];
V2D Base;
V2D Lv;
struct Node {
V2D point;
int type;
double angle;
} ns[M];
inline ld dis(const Wall& p) {
V2D L = p.a - p.b;
swap(L.x, L.y);
L.y = -L.y;
return abs(p.a*L) * Lv.len() / abs(L*Lv);
//return abs(p.a*L) / abs(L*Lv) * Lv.len();
//ld v = abs(p.a*L) / L.len();
//ld v2 = abs(L*Lv) / Lv.len() * v / L.len();
//printf("%.4Lf: %.4Lf!
", v, v2);
//return v * v / v2;
}
class WallComp
{
public:
inline bool operator()(const int& left, const int& right) const
{
double dx = dis(Walls[left]);
double dy = dis(Walls[right]);
return dx < dy;
}
};
set<int, WallComp> s;
inline bool equal(double x, double y) {
return fabs(x - y) < eps;
}
inline bool cmp(const Node &x, const Node &y) {
return equal(x.angle, y.angle) ? x.type > y.type : x.angle < y.angle;
}
int ct = 0;
inline Node& AddNode(V2D v, int t) {
Node &p = ns[ct++];
p.point = v;
p.angle = v.acos();
p.type = t;
return p;
}
int main() {
int T = 0;
while (io.rn(n) && io.rn(m) && io.rn(q)) {
printf("Case #%d:
", ++T);
for (int i = 1; i <= n; ++i) Enemies[i].read();
for (int i = 1; i <= m; ++i)
Walls[i].a.read(), Walls[i].b.read();
queue<int> ready_to;
while (q--) {
s.clear();
memset(ap, 0, sizeof(ap));
Base.read();
ct = 0;
for (int i = 1; i <= n; ++i)
Enemies[i] -= Base;
for (int i = 1; i <= m; ++i)
Walls[i].a -= Base, Walls[i].b -= Base;
for (int i = 1; i <= n; ++i) {
AddNode(Enemies[i], 0);
}
Lv = V2D(-1, 0);
ll dx = -1e9;
for (int i = 1; i <= m; ++i) {
AddNode(Walls[i].a, i);
AddNode(Walls[i].b, i);
V2D a = Walls[i].a;
V2D b = Walls[i].b;
if (min(a.y, b.y) >= 0)continue;
if (max(a.y, b.y) < 0)continue;
if (max(a.y, b.y) == 0) {
if (a.y == 0 && a.x < 0) {
s.insert(i);
ap[i] = true;
continue;
}
if (b.y == 0 && b.x < 0) {
s.insert(i);
ap[i] = true;
continue;
}
continue;
}
double dx = 1.0 * (abs(a.y)*b.x + abs(b.y)*a.x) / (abs(a.y) + abs(b.y));
if (dx < 0) {
s.insert(i); ap[i] = true;
}
}
sort(ns, ns + ct, cmp);
int cur = 0, ans = 0;
while (cur < ct) {
Lv = ns[cur].point;
double now = ns[cur].angle;
ld dx = 1e9;
bool flag = false;
while (cur < ct) {
if (fabs(ns[cur].angle - now) > eps)break;
if (ns[cur].type == 0) {
if (!flag) {
flag = true;
if (s.size() > 0) dx = min(dx, dis(Walls[*s.begin()]));
}
ld d = ns[cur].point.len();
if (d < dx)++ans;
++cur;
continue;
}
int t = ns[cur].type;
if (cur + 1 < ct && fabs(ns[cur + 1].angle - now) < eps && ns[cur + 1].type == t) {
dx = min(dx, min(ns[cur].point.len(), ns[cur + 1].point.len()));
cur += 2;
continue;
}
bool &x = ap[t];
if (x) {
ready_to.push(t);
}
else {
s.insert(t);
}
x ^= 1;
++cur;
}
while (ready_to.size() > 0) {
s.erase(ready_to.front());
ready_to.pop();
}
}
io.oln(ans);
for (int i = 1; i <= n; ++i)
Enemies[i] += Base;
for (int i = 1; i <= m; ++i)
Walls[i].a += Base, Walls[i].b += Base;
}
}
return 0;
}