| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 141229 |
2019-08-07T07:14:38 Z |
tutis |
Tri (CEOI09_tri) |
C++17 |
|
142 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()
{
if (A[0] != NULL)
return;
int xm = (x1 + x2) / 2;
int ym = (y1 + y2) / 2;
A[0] = new quad(x1, xm, y1, ym);
A[1] = new quad(x1, xm, ym + 1, y2);
A[2] = new quad(xm + 1, x2, y1, ym);
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();
for (int t = 0; t < 4; 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]->get(a, b) > 0)
return 1;
if (A[1]->get(a, b) > 0)
return 1;
if (A[2]->get(a, b) > 0)
return 1;
if (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";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
2336 KB |
Output is correct |
| 2 |
Correct |
36 ms |
3064 KB |
Output is correct |
| 3 |
Runtime error |
137 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
125 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
131 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
142 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
132 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
130 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
127 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
124 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
