#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
struct pnt{
int x, y, c;
int r1, r2;
}a[30005], s, e;
lint ccw(pnt a, pnt b, pnt c){
return 1ll * (b.x - a.x) * (c.y - a.y) - 1ll * (c.x - a.x) * (b.y - a.y);
}
int n, m;
int stx[30005], sty[30005], edx[30005], edy[30005];
void label1(){
sort(a, a+n, [&](const pnt &p, const pnt &q){
bool bh1 = ccw(s, e, p) > 0;
bool bh2 = ccw(s, e, q) > 0;
if(bh1 != bh2) return bh1 > bh2;
return ccw(s, p, q) > 0;
});
int dv = 0;
for(int i=0; i<n; i++){
a[i].r1 = i;
if(ccw(s, e, a[i]) > 0) dv = i+1;
}
int p = 0;
for(int i=dv; i<n; i++){
while(p < dv && ccw(s, a[i], a[p]) > 0) p++;
stx[i] = i;
edx[i] = p;
}
p = dv;
for(int i=0; i<dv; i++){
while(p < n && ccw(s, a[i], a[p]) > 0) p++;
stx[i] = p;
edx[i] = i;
}
}
void label2(){
sort(a, a+n, [&](const pnt &p, const pnt &q){
bool bh1 = ccw(s, e, p) > 0;
bool bh2 = ccw(s, e, q) > 0;
if(bh1 != bh2) return bh1 > bh2;
return ccw(e, p, q) > 0;
});
int dv = 0;
for(int i=0; i<n; i++){
a[i].r2 = i;
if(ccw(s, e, a[i]) > 0) dv = i+1;
}
int p = 0;
for(int i=dv; i<n; i++){
while(p < dv && ccw(e, a[i], a[p]) > 0) p++;
sty[i] = p;
edy[i] = i;
}
p = dv;
for(int i=0; i<dv; i++){
while(p < n && ccw(e, a[i], a[p]) > 0) p++;
sty[i] = i;
edy[i] = p;
}
}
vector<pi> grp[30005];
map<pi, int> mp;
int refer[30005], ans[30005];
void add_sweep(int sx, int ex, int sy, int ey, int gnum, int idx){
for(auto &i : grp[gnum]){
if(sx <= i.first && i.first <= ex && sy <= i.second && i.second <= ey) ans[idx]++;
}
}
void add_sweep2(int y, int gnum, int idx){
for(auto &i : grp[gnum]){
if(sty[i.second] <= y && y < edy[i.second]) ans[idx]++;
}
}
void add_sweep3(int x, int y, int gnum, int idx){
for(auto &i : grp[gnum]){
if(edx[i.first] <= x && x < stx[i.first] && sty[i.second] <= y && y < edy[i.second]) ans[idx]--;
}
}
int main(){
scanf("%d %d",&n,&m);
for(int i=0; i<n; i++){
scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].c);
}
scanf("%d %d %d %d",&s.x,&s.y,&e.x,&e.y);
label1();
label2();
for(int i=0; i<n; i++){
grp[a[i].c].push_back(pi(a[i].r1, a[i].r2));
}
int q;
scanf("%d",&q);
for(int i=1; i<=q; i++){
int x, y;
scanf("%d %d",&x,&y);
if(mp.find(pi(x, y)) != mp.end()){
refer[i] = mp[pi(x, y)];
continue;
}
int ret = 0, qi = i;
if(grp[x].size() < grp[y].size()){
for(auto &i : grp[x]){
add_sweep(0, edx[i.first] - 1, sty[i.second], edy[i.second] - 1, y, qi);
add_sweep(stx[i.first], n-1, sty[i.second], edy[i.second] - 1, y, qi);
}
}
else{
for(auto &j : grp[y]){
add_sweep2(j.second, x, i);
add_sweep3(j.first, j.second, x, i);
}
}
/*
for(auto &i : grp[x]){
for(auto &j : grp[y]){
bool xma = !(edx[i.first] <= j.first && j.first < stx[i.first]);
bool yma = (sty[i.second] <= j.second && j.second < edy[i.second]);
if(xma && yma) ret++;
}
}*/
mp[pi(x, y)] = i;
}
for(int i=1; i<=q; i++){
if(refer[i]) printf("%d\n", ans[refer[i]]);
else printf("%d\n", ans[i]);
}
}
Compilation message
dragon2.cpp: In function 'int main()':
dragon2.cpp:113:7: warning: unused variable 'ret' [-Wunused-variable]
int ret = 0, qi = i;
^
dragon2.cpp:94:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&m);
^
dragon2.cpp:96:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].c);
^
dragon2.cpp:98:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d",&s.x,&s.y,&e.x,&e.y);
^
dragon2.cpp:105:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&q);
^
dragon2.cpp:108:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&x,&y);
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
13 ms |
4028 KB |
Output is correct |
| 2 |
Correct |
23 ms |
4028 KB |
Output is correct |
| 3 |
Correct |
39 ms |
4424 KB |
Output is correct |
| 4 |
Runtime error |
79 ms |
7856 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1386 ms |
4428 KB |
Output is correct |
| 2 |
Correct |
2583 ms |
4456 KB |
Output is correct |
| 3 |
Correct |
79 ms |
4424 KB |
Output is correct |
| 4 |
Correct |
33 ms |
4424 KB |
Output is correct |
| 5 |
Correct |
29 ms |
4688 KB |
Output is correct |
| 6 |
Correct |
836 ms |
4428 KB |
Output is correct |
| 7 |
Correct |
923 ms |
4424 KB |
Output is correct |
| 8 |
Correct |
853 ms |
4368 KB |
Output is correct |
| 9 |
Correct |
649 ms |
4432 KB |
Output is correct |
| 10 |
Correct |
859 ms |
4368 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
13 ms |
4028 KB |
Output is correct |
| 2 |
Correct |
23 ms |
4028 KB |
Output is correct |
| 3 |
Correct |
39 ms |
4424 KB |
Output is correct |
| 4 |
Runtime error |
79 ms |
7856 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
