#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 3e4;
struct Point { ll x, y; };
Point operator + (const Point &p, const Point &q) { return {p.x+q.x, p.y+q.y}; }
Point operator - (const Point &p, const Point &q) { return {p.x-q.x, p.y-q.y}; }
ll ccw(Point p, Point q) { return p.x*q.y-p.y*q.x; }
ll ccw(Point p, Point q1, Point q2) { return ccw(q1-p, q2-p); }
int N, M, Q;
vector<Point> P[MAXN+10];
Point A, B;
map<pii, ll> memo;
struct Node
{
int val;
Node *lc, *rc;
Node() : val(0), lc(NULL), rc(NULL) {}
};
void makeTree(Node *node, int tl, int tr)
{
if(tl==tr) return;
int mid=tl+tr>>1;
node->lc=new Node();
node->rc=new Node();
makeTree(node->lc, tl, mid);
makeTree(node->rc, mid+1, tr);
}
bool cmpA(const Point &p, const Point &q)
{
if((A.x<p.x || (A.x==p.x && A.y>p.y)) && (A.x<q.x || (A.x==q.x && A.y>q.y))) return ccw(A, p, q)>0;
if((A.x>p.x || (A.x==p.x && A.y<p.y)) && (A.x>q.x || (A.x==q.x && A.y<q.y))) return ccw(A, p, q)>0;
if((A.x<p.x || (A.x==p.x && A.y>p.y)) && (A.x>q.x || (A.x==q.x && A.y<q.y))) return true;
if((A.x>p.x || (A.x==p.x && A.y<p.y)) && (A.x<q.x || (A.x==q.x && A.y>q.y))) return false;
}
bool cmpB(const Point &p, const Point &q)
{
if((B.x<p.x || (B.x==p.x && B.y>p.y)) && (B.x<q.x || (B.x==q.x && B.y>q.y))) return ccw(B, p, q)>0;
if((B.x>p.x || (B.x==p.x && B.y<p.y)) && (B.x>q.x || (B.x==q.x && B.y<q.y))) return ccw(B, p, q)>0;
if((B.x<p.x || (B.x==p.x && B.y>p.y)) && (B.x>q.x || (B.x==q.x && B.y<q.y))) return true;
if((B.x>p.x || (B.x==p.x && B.y<p.y)) && (B.x<q.x || (B.x==q.x && B.y>q.y))) return false;
}
struct Data
{
int S;
vector<Point> VA, VB;
vector<Node*> tree;
Node *addTree(Node *node, int tl, int tr, int pos)
{
if(pos<tl || tr<pos) return node;
Node *ret=new Node();
if(tl==tr)
{
ret->val=node->val+1;
return ret;
}
int mid=tl+tr>>1;
ret->lc=addTree(node->lc, tl, mid, pos);
ret->rc=addTree(node->rc, mid+1, tr, pos);
ret->val=ret->lc->val+ret->rc->val;
return ret;
}
int query(Node *nodel, Node *noder, int tl, int tr, int l, int r)
{
if(tr<l || r<tl) return 0;
if(l<=tl && tr<=r) return noder->val-nodel->val;
int mid=tl+tr>>1;
return query(nodel->lc, noder->lc, tl, mid, l, r)+query(nodel->rc, noder->rc, mid+1, tr, l, r);
}
void init()
{
int i, j;
S=VA.size();
if(S==0) return;
sort(VA.begin(), VA.end(), cmpA);
sort(VB.begin(), VB.end(), cmpB);
vector<pair<Point, int>> VAT, VBT;
for(i=0; i<S; i++) VAT.push_back({VA[i], i});
for(i=0; i<S; i++) VBT.push_back({VB[i], i});
sort(VAT.begin(), VAT.end(), [&](const pair<Point, int> &p, const pair<Point, int> &q) { return pll(p.first.x, p.first.y)<pll(q.first.x, q.first.y); });
sort(VBT.begin(), VBT.end(), [&](const pair<Point, int> &p, const pair<Point, int> &q) { return pll(p.first.x, p.first.y)<pll(q.first.x, q.first.y); });
vector<pii> V;
for(i=0; i<S; i++)
{
int x=VAT[i].second+1, y=VBT[i].second+1;
//printf("!(%d %d) : %d %d\n", VAT[i].first.x, VAT[i].first.y, x, y);
V.push_back({x, y});
}
sort(V.begin(), V.end());
tree.push_back(new Node());
makeTree(tree[0], 1, S);
for(i=0; i<S; i++) tree.push_back(addTree(tree.back(), 1, S, V[i].second));
}
int query(Point pxl, Point pxr, Point pyl, Point pyr)
{
if(S==0) return 0;
int xl=(lower_bound(VA.begin(), VA.end(), pxl, cmpA)-VA.begin())%S+1;
int xr=(upper_bound(VA.begin(), VA.end(), pxr, cmpA)-VA.begin()-1+S)%S+1;
int yl=(lower_bound(VB.begin(), VB.end(), pyl, cmpB)-VB.begin())%S+1;
int yr=(upper_bound(VB.begin(), VB.end(), pyr, cmpB)-VB.begin()-1+S)%S+1;
//printf("QUERYQUERYNK %d %d %d %d\n", xl, xr, yl, yr);
if(!(ccw(A, pxl, VA[xl-1])>=0 && ccw(A, VA[xl-1], pxr)>=0)) return 0;
if(!(ccw(A, pxl, VA[xr-1])>=0 && ccw(A, VA[xr-1], pxr)>=0)) return 0;
if(!(ccw(B, pyl, VB[yl-1])>=0 && ccw(B, VB[yl-1], pyr)>=0)) return 0;
if(!(ccw(B, pyl, VB[yr-1])>=0 && ccw(B, VB[yr-1], pyr)>=0)) return 0;
//printf("!\n");
int ret=0;
if(xl<=xr)
{
if(yl<=yr)
{
ret+=query(tree[xl-1], tree[xr], 1, S, yl, yr);
}
else
{
ret+=query(tree[xl-1], tree[xr], 1, S, yr, S);
ret+=query(tree[xl-1], tree[xr], 1, S, 1, yl);
}
}
else
{
if(yl<=yr)
{
ret+=query(tree[0], tree[xl], 1, S, yl, yr);
ret+=query(tree[xr-1], tree[S], 1, S, yl, yr);
}
else
{
ret+=query(tree[0], tree[xl], 1, S, yr, S);
ret+=query(tree[0], tree[xl], 1, S, 1, yl);
ret+=query(tree[xr-1], tree[S], 1, S, yr, S);
ret+=query(tree[xr-1], tree[S], 1, S, 1, yl);
}
}
//printf("QUERY %d %d %d %d : %d\n", xl, xr, yl, yr, ret);
return ret;
}
};
Data D[MAXN+10];
int main()
{
int i, j;
scanf("%d%d", &N, &M);
for(i=1; i<=N; i++)
{
int x, y, w;
scanf("%d%d%d", &x, &y, &w);
P[w].push_back({x, y});
}
scanf("%lld%lld%lld%lld", &A.x, &A.y, &B.x, &B.y);
for(i=1; i<=M; i++)
{
for(auto it : P[i])
{
D[i].VA.push_back(it);
D[i].VB.push_back(it);
}
D[i].init();
//printf("-> %d\n", i);
}
scanf("%d", &Q);
while(Q--)
{
int s, e;
ll ans=0;
scanf("%d%d", &s, &e);
if(true)
{
for(auto it : P[s])
{
Point pxl, pxr, pyl, pyr;
pxl=it, pxr={2*A.x-it.x, 2*A.y-it.y};
pyl=it, pyr={2*B.x-it.x, 2*B.y-it.y};
if(ccw(A, it, B)<0) swap(pxl, pxr);
if(ccw(B, it, A)<0) swap(pyl, pyr);
//printf("%lld %lld / %lld %lld / %lld %lld / %lld %lld -> \n", pxl.x, pxl.y, pxr.x, pxr.y, pyl.x, pyl.y, pyr.x, pyr.y);
int t=D[e].query(pxl, pxr, pyl, pyr);
//printf("-> %d\n", t);
ans+=t;
}
}
printf("%lld\n", ans);
}
}
Compilation message
dragon2.cpp: In function 'void makeTree(Node*, int, int)':
dragon2.cpp:33:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
dragon2.cpp: In member function 'Node* Data::addTree(Node*, int, int, int)':
dragon2.cpp:71:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
dragon2.cpp: In member function 'int Data::query(Node*, Node*, int, int, int, int)':
dragon2.cpp:82:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
dragon2.cpp: In member function 'void Data::init()':
dragon2.cpp:87:10: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
dragon2.cpp: In function 'int main()':
dragon2.cpp:166:9: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
dragon2.cpp: In function 'bool cmpA(const Point&, const Point&)':
dragon2.cpp:46:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
dragon2.cpp: In function 'bool cmpB(const Point&, const Point&)':
dragon2.cpp:54:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
dragon2.cpp: In function 'int main()':
dragon2.cpp:168:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~
dragon2.cpp:172:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &x, &y, &w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:175:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld%lld", &A.x, &A.y, &B.x, &B.y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:188:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &Q);
~~~~~^~~~~~~~~~
dragon2.cpp:193:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &s, &e);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
4984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
97 ms |
21724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
4984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
