#include <bits/stdc++.h>
#define kyou using
#define mo namespace
#define kawaii std
kyou mo kawaii; // hi honey~
#define ll long long
#define ld long double
#define endl "\n"
const int MX = 100005;
const int LG = (int)log2(MX) + 1;
const int BLOCK = 205;
const int inf = 1000000069;
const ll inf_ll = 8000000000000000069ll;
const ll mod = 1e9 + 7;
const int dxh[] = {1, 1, -1, -1, 2, 2, -2, -2};
const int dyh[] = {2, -2, 2, -2, 1, -1, 1, -1}; // horse
const int dx[] = {0, 1, 0, -1, 0, 0};
const int dy[] = {1, 0, -1, 0, 0, 0}; // adj
const int dz[] = {0, 0, 0, 0, 1, -1}; // 3d
const int dxd[] = {1, 1, 1, 0, -1, -1, -1, 0};
const int dyd[] = {1, 0, -1, -1, -1, 0, 1, 1}; // diag
#define min(x, y) (x < y ? x : y)
#define max(x, y) (x > y ? x : y)
bool untied = 0;
void setIn(string s){freopen(s.c_str(), "r", stdin);}
void setOut(string s){freopen(s.c_str(), "w", stdout);}
void unsyncIO(){cin.tie(0) -> sync_with_stdio(0);}
void setIO(string s = ""){
if(!untied) unsyncIO(), untied = 1;
if(s.size()){
setIn(s + ".in");
setOut(s + ".out");
}
}
struct point{
ll x, y;
point& operator-=(const point &a){
x -= a.x; y -= a.y;
return *this;
}
friend point operator-(point a, const point &b){return a -= b;}
};
inline ll cross(point A, point B){
return A.x * 1ll * B.y - A.y * 1ll * B.x;
}
inline ll mag2(point A){
return A.x * 1ll * A.x + A.y * 1ll * A.y;
}
int n, q;
vector<point> points;
vector<point> hullify(vector<point> x){
vector<point> nw;
for(point i : x){
if(nw.size() && cross(nw.back(), i) == 0) continue;
nw.push_back(i);
while(nw.size() >= 3 && cross(nw[nw.size() - 1] - nw[nw.size() - 2], nw[nw.size() - 2] - nw[nw.size() - 3]) >= 0){
point tp = nw.back(); nw.pop_back(); nw.pop_back();
nw.push_back(tp);
}
}
return nw;
}
vector<point> st[MX * 4];
void build(int nd, int cl, int cr){
for(int i = cl; i <= cr; i ++)
st[nd].push_back(points[i]);
st[nd] = hullify(st[nd]);
if(cl != cr){
build(nd * 2, cl, (cl + cr) / 2);
build(nd * 2 + 1, (cl + cr) / 2 + 1, cr);
}
}
bool query(int nd, int cl, int cr, point L, point R){
if(cross(st[nd].back(), L) < 0 || cross(R, st[nd][0]) < 0) return 0;
if(cross(L, st[nd][0]) < 0 && cross(st[nd].back(), R) < 0){
int lf = 0, rg = st[nd].size() - 1;
for(int md, md2; lf < rg;){
md = (lf + rg) / 2;
md2 = md + 1;
if(cross(R - L, st[nd][md] - L) < cross(R - L, st[nd][md2] - L))
rg = md;
else
lf = md + 1;
}
if(cross(R - L, st[nd][lf] - L) < 0) return 1;
else return 0;
}
if(cl != cr){
bool lf = query(nd * 2, cl, (cl + cr) / 2, L, R);
bool rg = query(nd * 2 + 1, (cl + cr) / 2 + 1, cr, L, R);
return (lf | rg);
}
return 0;
}
int main(){
setIO();
cin >> n >> q;
points.resize(n);
for(int i = 0; i < n; i ++)
cin >> points[i].x >> points[i].y;
sort(points.begin(), points.end(), [&](point a, point b){
if(cross(a, b) == 0)
return mag2(a) < mag2(b);
return cross(a, b) < 0;
});
build(1, 0, n - 1);
point A, B;
for(int i = 0; i < q; i ++){
cin >> A.x >> A.y >> B.x >> B.y;
if(cross(A, B) > 0) swap(A, B);
if(query(1, 0, n - 1, A, B)) cout << "Y\n";
else cout << "N\n";
}
return 0;
}
Compilation message
tri.cpp: In function 'void setIn(std::string)':
tri.cpp:29:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
29 | void setIn(string s){freopen(s.c_str(), "r", stdin);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
tri.cpp: In function 'void setOut(std::string)':
tri.cpp:30:30: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
30 | void setOut(string s){freopen(s.c_str(), "w", stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
9812 KB |
Output is correct |
| 2 |
Correct |
6 ms |
9848 KB |
Output is correct |
| 3 |
Correct |
42 ms |
14612 KB |
Output is correct |
| 4 |
Correct |
79 ms |
24140 KB |
Output is correct |
| 5 |
Correct |
177 ms |
38072 KB |
Output is correct |
| 6 |
Correct |
239 ms |
24008 KB |
Output is correct |
| 7 |
Correct |
326 ms |
28216 KB |
Output is correct |
| 8 |
Correct |
259 ms |
29780 KB |
Output is correct |
| 9 |
Correct |
301 ms |
31508 KB |
Output is correct |
| 10 |
Correct |
329 ms |
33448 KB |
Output is correct |
