제출 #230817

#제출 시각아이디문제언어결과실행 시간메모리
230817walnutwaldo20Relay (COI16_relay)C++14
0 / 100
5 ms384 KiB
#include <bits/stdc++.h> #define F0R(i, a) for (int i = 0; i < (int)(a); i++) #define PB push_back #define MP make_pair #define X real() #define Y imag() #define F first #define S second using namespace std; typedef long long ll; typedef long double ld; typedef complex<ld> point; typedef pair<point, point> edge; #define MAXN 100000 bool reaches[MAXN]; edge rev(edge e) { return MP(e.S, e.F); } ll crossp(point p1, point p2) { return (conj(p1) * p2).Y; } ll dotp(point p1, point p2) { return (conj(p1) * p2).X; } bool rightof(point p, edge e) { bool ret = crossp(e.S - e.F, p - e.S) <= 0; return ret; } point get(vector<point>& v, int idx) { return v[(idx % (int)v.size() + (int)v.size()) % (int)v.size()]; } bool inside(point p, vector<point>& hull) { F0R(i, hull.size()) { edge e = MP(hull[i], get(hull, i + 1)); if (rightof(p, e)) { return false; } } return true; } point findtangent(vector<point>&hull, point p, bool seen1, bool seen2) { F0R(i, hull.size()) { edge edge1 = MP(get(hull, i - 1), hull[i]); edge edge2 = MP(hull[i], get(hull, i + 1)); if (rightof(p, edge1) == seen1 && rightof(p, edge2) == seen2) { return hull[i]; } } cout << "this should not print" << endl; exit(0); } ld cosbw(point e1, point e2) { ld res = dotp(e1, e2); res /= abs(e1); res /= abs(e2); return res; } edge findfarthest(vector<point>& candidates, edge tangent, int dir, vector<point>& hull) { int idx = 0; F0R(i, hull.size()) if (hull[i] == tangent.S) { idx = i; } edge res = tangent; ld mincos = 1; for (const point p : candidates) { edge prevedge = MP(get(hull, idx - dir), hull[idx]); if (dir < 0) { prevedge = rev(prevedge); } if (!rightof(p, prevedge)) { continue; } edge curr = MP(p, hull[idx]); while (1) { edge e = MP(hull[idx], get(hull, idx + dir)); if (dir < 0) { e = rev(e); } if (rightof(p, e)) { idx = ((idx + dir) % hull.size() + hull.size()) % hull.size(); curr = MP(p, get(hull, idx)); } else { break; } } ld c = cosbw(curr.S - curr.F, tangent.S - tangent.F); if (c < mincos) { res = curr; mincos = c; } } return res; } void read(int& len, vector<point>& vec) { cin >> len; F0R(i, len) { ll x, y; cin >> x >> y; vec.PB(point(x, y)); } } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; vector<point> v, hull; read(n, v); read(m, hull); point righttangent = findtangent(hull, v[0], true, false); point lefttangent = findtangent(hull, v[0], false, true); vector<point> triangle; triangle.PB(v[0]); triangle.PB(righttangent); triangle.PB(lefttangent); vector<point> leftpoints, rightpoints; F0R(i, v.size()) { if (inside(v[i], triangle)) { reaches[i] = true; } if (rightof(v[i], MP(v[0], righttangent))) { reaches[i] = true; rightpoints.PB(v[i]); } if (rightof(v[i], MP(lefttangent, v[0]))) { reaches[i] = true; leftpoints.PB(v[i]); } } edge farthestleft = findfarthest(leftpoints, MP(v[0], lefttangent), -1, hull); edge farthestright = findfarthest(rightpoints, MP(v[0], righttangent), 1, hull); vector<point> lefttriangle; lefttriangle.PB(farthestleft.F); lefttriangle.PB(lefttangent); lefttriangle.PB(farthestleft.S); vector<point> righttriangle; righttriangle.PB(farthestright.F); righttriangle.PB(farthestright.S); righttriangle.PB(righttangent); F0R(i, v.size()) { if (rightof(v[i], rev(farthestleft))) { reaches[i] = true; } if (rightof(v[i], farthestright)) { reaches[i] = true; } if (inside(v[i], lefttriangle)) { reaches[i] = true; } if (inside(v[i], righttriangle)) { reaches[i] = true; } } int res = 0; F0R(i, n) if (reaches[i]) { res++; } cout << res - 1 << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...