#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 time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| 10 |
Execution timed out |
2091 ms |
384 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| 10 |
Execution timed out |
2091 ms |
384 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| 10 |
Execution timed out |
2091 ms |
384 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| 10 |
Execution timed out |
2091 ms |
384 KB |
Time limit exceeded |
