| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 141236 |
2019-08-07T07:21:31 Z |
tutis |
Tri (CEOI09_tri) |
C++17 |
|
2000 ms |
65540 KB |
/*input
4 3
1 2
1 3
5 1
5 3
1 4 3 3
2 2 4 1
4 4 6 3
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct point
{
ll x, y;
point() {}
point(ll x, ll y): x(x), y(y) {}
};
point operator-(point a, point b)
{
return point(a.x - b.x, a.y - b.y);
}
point operator-(point b)
{
return point(-b.x, -b.y);
}
ll cross(point a, point b)
{
return a.x * b.y - a.y * b.x;
}
int sgn(ll x)
{
if (x < 0)
return -1;
if (x > 0)
return 1;
return 0;
}
int viduj(point x, point a, point b)
{
if (sgn(cross(a, x)) != sgn(cross(x, b)))
return 0;
if (sgn(cross(b - a, x - a)) != sgn(cross(x - a, -a)))
return 0;
return 1;
}
struct quad
{
int x1, x2;
int y1, y2;
int kiek = 0;
quad* A[4] = {NULL, NULL, NULL, NULL};
quad(int a1 = 0, int a2 = (1 << 30) - 1, int b1 = 0, int b2 = (1 << 30) - 1):
x1(a1), x2(a2), y1(b1), y2(b2)
{
}
void fix(int x, int y)
{
int xm = (x1 + x2) / 2;
int ym = (y1 + y2) / 2;
int t = 0;
if (x > xm)
t += 2;
if (y > ym)
t++;
if (t == 0 && A[0] == NULL)
A[0] = new quad(x1, xm, y1, ym);
if (t == 1 && A[1] == NULL)
A[1] = new quad(x1, xm, ym + 1, y2);
if (t == 2 && A[2] == NULL)
A[2] = new quad(xm + 1, x2, y1, ym);
if (t == 3 && A[3] == NULL)
A[3] = new quad(xm + 1, x2, ym + 1, y2);
}
void add(int x, int y)
{
if (x1 > x || x > x2 || y1 > y || y > y2)
return;
kiek++;
if (x1 == x2)
return;
fix(x, y);
for (int t = 0; t < 4; t++)
if (A[t])
A[t]->add(x, y);
}
int get(point a, point b)
{
if (kiek == 0)
return 0;
int s1 = sgn(cross(b - a, point(x1, y1) - a));
int s2 = sgn(cross(b - a, point(x1, y2) - a));
int s3 = sgn(cross(b - a, point(x2, y1) - a));
int s4 = sgn(cross(b - a, point(x2, y2) - a));
int s5 = sgn(cross(b - a, -a));
if (s1 == s2 && s2 == s3 && s3 == s4 && s4 == -s5)
return 0;
s1 = sgn(cross(b, point(x1, y1)));
s2 = sgn(cross(b, point(x1, y2)));
s3 = sgn(cross(b, point(x2, y1)));
s4 = sgn(cross(b, point(x2, y2)));
s5 = -sgn(cross(b, a));
if (s1 == s2 && s2 == s3 && s3 == s4 && s4 == s5)
return 0;
s1 = sgn(cross(a, point(x1, y1)));
s2 = sgn(cross(a, point(x1, y2)));
s3 = sgn(cross(a, point(x2, y1)));
s4 = sgn(cross(a, point(x2, y2)));
s5 = -sgn(cross(a, b));
if (s1 == s2 && s2 == s3 && s3 == s4 && s4 == s5)
return 0;
if (x1 == x2)
return viduj(point(x1, y1), a, b);
if (A[0] && A[0]->get(a, b) > 0)
return 1;
if (A[1] && A[1]->get(a, b) > 0)
return 1;
if (A[2] && A[2]->get(a, b) > 0)
return 1;
if (A[3] && A[3]->get(a, b) > 0)
return 1;
return 0;
}
} medis;
int main()
{
int K, M;
cin >> K >> M;
while (K--)
{
int x, y;
cin >> x >> y;
medis.add(x, y);
}
while (M--)
{
point A, B;
cin >> A.x >> A.y >> B.x >> B.y;
if (medis.get(A, B) > 0)
cout << "Y\n";
else
cout << "N\n";
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
860 KB |
Output is correct |
| 2 |
Correct |
26 ms |
992 KB |
Output is correct |
| 3 |
Correct |
264 ms |
32664 KB |
Output is correct |
| 4 |
Execution timed out |
2089 ms |
60304 KB |
Time limit exceeded |
| 5 |
Runtime error |
229 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 6 |
Execution timed out |
2089 ms |
61676 KB |
Time limit exceeded |
| 7 |
Runtime error |
243 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
233 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
238 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
234 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
