이 문제는 nhn 특별상이 걸려있었던 문제로, 문제 설명에 nhn 이 도배(?)되어있는것으로 미루어 짐작할 수 있었습니다. -0-
문제를 간단히 설명하면,
"n ( 1 <= n <= 100,000) 개의 혜성이 (xi, yi) 라는 좌표로 부터 단위시간당 (dxi, dyi) 라는 속도로 움직일때, 특정시간에 (0,0)-(w,h) 의 직사각형 프레임안에 동시에 들어가는 최대 혜성의 갯수를 찾는문제"
라고 할 수 있습니다. 이 때, 혜성이 프레임 안에 들어가는 것은 프레임 외곽선에 걸치지 않고 완전히 포함되는 경우를 말합니다.
이 문제는 O(nlgn) 의 시간복잡도로 해결이 가능합니다.
먼저 각 혜성에 대하여 프레임 내에서 머무는 시간을 구하여, 진입시간과 이탈시간을 찾습니다. 이때 구해지는 시간들은 모두 프레임 외곽선과 만나는 시간을 기준으로 하기 때문에, 혜성의 초기위치가 프레임 안에 완전히 포함되는 경우는 진입시간을 0 이 아닌 음수 시간으로 고려해야합니다. 이렇게 구한 값들을 시간에 대하여 정렬한 후, 순차적으로 혜성의 진입때는 +1, 이탈때는 -1 을 하면서 음수가 아닌 시간대에 머무는 최대의 혜성 갯수를 구해주면 문제에서 원하는 답을 구할 수 있습니다.
~~~ cpp

typedef long long ll;
struct Frac {
int a, b;
bool operator < (const Frac &r) const {
return (ll)a * (ll)r.b < (ll)r.a * (ll)b;
}
bool operator > (const Frac &r) const {
return (ll)a * (ll)r.b > (ll)r.a * (ll)b;
}
bool operator == (const Frac &r) const {
return a == r.a && b == r.b;
}
bool operator != (const Frac &r) const {
return a != r.a || b != r.b;
}
};
struct shot {
Frac t;
int diff;
bool operator < (const shot &r) const {
if (t != r.t) return t < r.t;
return diff < r.diff;

}
bool operator == (const shot &r) const {
return t == r.t && diff == r.diff;
}
};
int gcd(int a, int b) {
return (b == 0 ? a : gcd(b, a%b));
}
Frac getCrossTime(int ix, int vx, int xx) { // x축 또는 y축과 만나는 시간을 구함
Frac f;
if (vx == 0) {
f.a = -1; f.b = 1;
}
else {
int g = gcd(abs(xx-ix), abs(vx));
f.a = (xx-ix) / g;
f.b = vx / g;
if (vx < 0) {
f.a *= -1; f.b *= -1;

}
}
return f;

}
bool Between(int ix, int vx, Frac t, int a, int b) { // 특정시간 t 에서 x 또는 y 좌표가 범위내에 포함되는지 확인
ll la, lb, lc;
la = (ll)a * (ll)t.b;
lb = (ll)b * (ll)t.b;
lc = (ll)ix * (ll)t.b + (ll)vx * (ll)t.a;
return (la <= lc && lc <= lb);
}
int main() {
int t, n, i;
int w, h, x, y, dx, dy;
int meteor;
Frac ct, mint, maxt;
vector v;
shot s;
int maxshot;
scanf("%d", &t);
while(t--) {
scanf("%d %d", &w, &h);
scanf("%d", &n);
v.clear();
meteor = 0;
for(i = 0; i < n; i++) {
scanf("%d %d %d %d", &x, &y, &dx, &dy);
if (x > 0 && y > 0 && x < w && y < h) meteor++; // 시간 0.0 에 이미 내부에 완전히 포함되어 있는 혜성의 갯수 체크
mint.a = 1e+9; mint.b = 1;
maxt.a = -mint.a; maxt.b = 1;
if ((x == 0 && dx == 0) || (x == w && dx == 0) || (y == 0 && dy == 0) || (y == h && dy == 0)) // 혜성이 외곽선을 타고 이동할 경우 무시
continue;
ct = getCrossTime(x, dx, 0); // left line crossing time
if (ct.a >= 0 && Between(y, dy, ct, 0, h)) {
mint = min(mint, ct);
maxt = max(maxt, ct);
}
ct = getCrossTime(x, dx, w); // right line crossing time
if (ct.a >= 0 && Between(y, dy, ct, 0, h)) {
mint = min(mint, ct);
maxt = max(maxt, ct);
}
ct = getCrossTime(y, dy, 0); // bottom line crossing time
if (ct.a >= 0 && Between(x, dx, ct, 0, w)) {
mint = min(mint, ct);
maxt = max(maxt, ct);
}
ct = getCrossTime(y, dy, h); // top line crossing time
if (ct.a >= 0 && Between(x, dx, ct, 0, w)) {
mint = min(mint, ct);
maxt = max(maxt, ct);
}
if (maxt < mint) continue; // 혜성이 프레임 내에 진입하지 않음
if (mint == maxt && x > 0 && y > 0 && x < w && y < h) { // 혜성이 내부에 있다가 이탈하는 경우
s.t = maxt; s.diff = -1;
v.push_back(s);
}
if (mint < maxt) {
s.t = mint; s.diff = 1; // 혜성진입시간
v.push_back(s);
s.t = maxt; s.diff = -1; // 혜성이탈시간
v.push_back(s);
}
}
sort(v.begin(), v.end());
maxshot = meteor;
for(i = 0; i < v.size(); i++) {
meteor += v[i].diff; // 시간 0.0 부터 진입할경우에는 1 증가, 이탈시에는 1 감소
maxshot = max(maxshot, meteor); // 동일 시간내에 이탈하는 혜성부터 계산되므로 답이 보장됨
}
printf("%d\n", maxshot);
}
return 0;
}

<div>[이 글은 과거 홈페이지에서 이전된 글입니다. <a href="http://algospot.andromeda-express.com/zbxe/editorial/5134">원문보기</a>]</div>