| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 157477 |
2019-10-11T21:28:50 Z |
mosesmayer |
Tri (CEOI09_tri) |
C++17 |
|
72 ms |
65540 KB |
#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
using namespace std;
typedef long long LL; typedef vector<int> vi; typedef pair<int,int> pii;
template<class F, class S> ostream& operator<< (ostream& os, const pair<F,S> p){os << '{' << p.fi << ", " << p.se << '}'; return os;}
const int INF = 0x3f3f3f3f;
struct Point{
LL x, y;
Point(){}
Point(LL x, LL y): x(x), y(y) {}
Point operator+ (const Point &rhs) const{
return Point(x + rhs.x, y + rhs.y);
}
Point operator- (const Point &rhs) const{
return Point(x - rhs.x, y - rhs.y);
}
LL operator* (const Point &rhs) const {
return x * rhs.y - rhs.x * y;
}
bool operator< (const Point &rhs) const{
LL c = x * rhs.y - rhs.x * y;
return c == 0 ? x < rhs.x : c > 0;
}
bool operator> (const Point &rhs) const{
return rhs < *this;
}
bool operator== (const Point &rhs) const{
return x == rhs.x && y == rhs.y;
}
};
void operator>> (istream &is, Point &p){
is >> p.x >> p.y;
}
ostream& operator<< (ostream& os, const Point &p){
os << '(' << p.x << ", " << p.y << ')';
return os;
}
LL ccw(Point A, Point B, Point C){
LL u = (B-A)*(C-A);
return u == 0 ? 0 : u > 0 ? 1 : -1;
}
int k, m, n;
Point tompel[100500];
pair<Point, Point> tri[100500];
map<Point, int> mp;
bool ans[100500];
namespace RangeTree{
struct node{
int lft, rgh;
vector<Point> hull;
node():lft(-1), rgh(-1), hull(0) {}
} tree[2500000];
int sz = 0;
void init(){
tree[sz++] = node();
}
void insert(int pos, Point pt, int p, int l, int r){
if (l == r){
tree[p].hull.push_back(pt);
tree[p].hull.push_back(Point(INF,INF));
return;
}
int md = (l + r) >> 1;
if (pos <= md){
if (tree[p].lft == -1) tree[p].lft = sz++;
insert(pos, pt, tree[p].lft, l, md);
} else {
if (tree[p].rgh == -1) tree[p].rgh = sz++;
insert(pos, pt, tree[p].rgh, md+1, r);
}
}
vector<Point> tmp;
bool andrew(Point x, Point y){
return x.x == y.x ? x.y < y.y : x.x < y.x;
}
void chull(int p, int l, int r){
if (p == -1) return;
if (l == r) return;
int md = (l + r) >> 1;
chull(tree[p].lft, l, md);
chull(tree[p].rgh, md+1, r);
if (tree[p].lft != -1) for (Point &pt : tree[tree[p].lft].hull) tmp.pb(pt);
if (tree[p].rgh != -1) for (Point &pt : tree[tree[p].rgh].hull) tmp.pb(pt);
sort(tmp.begin(), tmp.end(), andrew);
int k = 0;
for (int i = 0; i < tmp.size(); i++){
while (k >= 2 && ccw(tree[p].hull[k-2], tree[p].hull[k-1], tmp[i])<=0){
k--; tree[p].hull.pop_back();
}
tree[p].hull.push_back(tmp[i]); k++;
}
tmp.clear();
}
bool check(Point P, Point Q, Point A, Point B){ // returns if P is higher than Q w.r.t. segment AB
Point vAB = B - A, vAP = P - A, vAQ = Q - A;
return vAB * vAP > vAB * vAQ;
}
bool query(int i, int j, Point PA, Point PB, int p = 0, int l = 1, int r = n){
if (p == -1) return 0;
if (j < l || i > r) return 0;
if (i <= l && j >= r){
if (tree[p].hull.empty()) return 0;
int lo = 0, hi = int(tree[p].hull.size()) - 1, ans = -1;
while (lo <= hi){
int md = (lo + hi) >> 1;
if (check(tree[p].hull[md], tree[p].hull[md+1], PA, PB)){ // if higher then go to right range to get lower
lo = md + 1;
} else{
ans = md; hi = md - 1;
}
}
if (ans == -1) return 0;
return (PB-PA) * (tree[p].hull[ans]-PA) < 0;
}
int md = (l + r) >> 1;
return query(i, j,PA,PB, tree[p].lft, l, md) || query(i, j,PA,PB, tree[p].rgh, md+1, r);
}
}
int main(){
FASTIO;
cin >> k >> m;
for (int i = 1; i<= k; i++){
cin >> tompel[i].x >> tompel[i].y;
mp[tompel[i]];
}
for (int i = 1; i <= m; i++){
cin >> tri[i].first.x >> tri[i].first.y; cin >> tri[i].second.x >> tri[i].second.y;
mp[tri[i].first]; mp[tri[i].second];
if (tri[i].first > tri[i].second) swap(tri[i].first, tri[i].se);
}
int cnt = 0;
for (map<Point, int>::iterator it = mp.begin(); it != mp.end(); it++){
it -> se = ++cnt;
}
n = k + 2 * m;
RangeTree::init();
for (int i = 1; i <= k; i++){
RangeTree::insert(mp[tompel[i]], tompel[i], 0, 1, n);
}
RangeTree::chull(0, 1, n);
for (int i = 1; i <= m; i++){
ans[i] = RangeTree::query(mp[tri[i].first], mp[tri[i].se], tri[i].se, tri[i].fi);
}
for (int i = 1; i <= m; i++)
cout << (ans[i] ? 'Y' : 'N') << '\n';
return 0;
}
Compilation message
tri.cpp: In function 'void RangeTree::chull(int, int, int)':
tri.cpp:97:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < tmp.size(); i++){
~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
65 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
63 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
71 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
72 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
62 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
62 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
66 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
62 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
63 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
63 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
