Challenge: Good Point
Scor cont: 70.0 / 70
Submission status: Accepted
Submission score: 1.0
Submission ID: 464757609
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/good-point/problem
Cerinta
**The scoring system for this challenge is binary. Your score is zero unless you pass all tests.**
Given $n$ *strictly convex* simple polygons and $m$ ellipses on a plane, find any point lying in their intersection. Then print two lines of output, where the first line contains the point's $x$ coordinate and the second line contains its $y$ coordinate. The point lying on the boundary of an ellipse or polygon is considered to be an *inner* point.Input Format
The first line contains an integer, $n$, denoting the number of polygons.
The next set of lines defines $n$ polygons, where each polygon $i$ is described as follows:
- The first line contains an integer, $v_i$, denoting the number of vertices in polygon $i$.
- Each of the $v_i$ subsequent lines contains two space-separated integers denoting the respective $x$ and $y$ coordinates for one of polygon $i$'s vertices. The list of vertices is given in *counterclockwise* order.
The next line contains an integer, $m$, denoting the number of ellipses.
Each of the $m$ subsequent lines contains five space-separated integers denoting the respective values of $x_1$, $y_1$, $x_2$, $y_2$, and $a$, which are the coordinates of the two focal points and the semi-major-axis for an [Ellipse](https://en.wikipedia.org/wiki/Ellipse).Output Format
Print two lines describing an $(x, y)$ point inside the intersection. The first line must be a real number denoting the point's $x$ coordinate, and the second line must be a real number denoting its $y$ coordinate. Your answer is considered to be correct if there is a point, $(x_0, y_0)$, inside the intersection such that the distance between $(x, y)$ and $(x_0, y_0)$ is *at most* $10^{-4}$.Constraints
- $1 \le n \le 500$
- $3 \le v_i \le 1500$
- $3 \le \sum\limits_{i=0}^{n-1} v_i \le 1500$
- $1 \le m \le 1500$
- The coordinates of points are integers in the inclusive range $[-10^4, 10^4]$.
- All semi-major-axes are integers $\le 10^4$.
- It's guaranteed that a solution exists.
- This challenge has binary scoring.Cod sursa
#include <bits/stdc++.h>
using namespace std;
struct Edge {
double ax, ay;
double dx, dy;
double gx, gy; // gradient of violation -cross: (dy, -dx)
double norm2;
};
struct Ellipse {
double x1, y1, x2, y2;
double a2; // 2a
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<Edge> edges;
edges.reserve(2000);
double sx = 0.0, sy = 0.0;
int sc = 0;
for (int pi = 0; pi < n; ++pi) {
int v;
cin >> v;
vector<pair<double, double>> p(v);
for (int i = 0; i < v; ++i) {
cin >> p[i].first >> p[i].second;
sx += p[i].first;
sy += p[i].second;
++sc;
}
for (int i = 0; i < v; ++i) {
auto A = p[i];
auto B = p[(i + 1) % v];
double dx = B.first - A.first;
double dy = B.second - A.second;
double norm2 = dx * dx + dy * dy;
edges.push_back({A.first, A.second, dx, dy, dy, -dx, norm2});
}
}
int m;
cin >> m;
vector<Ellipse> ell(m);
for (int i = 0; i < m; ++i) {
double x1, y1, x2, y2, a;
cin >> x1 >> y1 >> x2 >> y2 >> a;
ell[i] = {x1, y1, x2, y2, 2.0 * a};
}
auto maxViolation = [&](double x, double y) {
double mv = 0.0;
for (const auto &e : edges) {
double cross = e.dx * (y - e.ay) - e.dy * (x - e.ax);
if (cross < 0.0) mv = max(mv, -cross);
}
for (const auto &e : ell) {
double d1 = hypot(x - e.x1, y - e.y1);
double d2 = hypot(x - e.x2, y - e.y2);
mv = max(mv, d1 + d2 - e.a2);
}
return mv;
};
double x = (sc ? sx / sc : 0.0);
double y = (sc ? sy / sc : 0.0);
const double EPS = 1e-10;
// Phase 1: cyclic subgradient projections.
for (int it = 0; it < 30000; ++it) {
double mv = 0.0;
for (const auto &e : edges) {
double cross = e.dx * (y - e.ay) - e.dy * (x - e.ax);
if (cross < 0.0) {
double v = -cross;
mv = max(mv, v);
double step = v / e.norm2;
x -= step * e.gx;
y -= step * e.gy;
}
}
for (const auto &e : ell) {
double vx1 = x - e.x1, vy1 = y - e.y1;
double vx2 = x - e.x2, vy2 = y - e.y2;
double d1 = hypot(vx1, vy1);
double d2 = hypot(vx2, vy2);
double v = d1 + d2 - e.a2;
if (v > 0.0) {
mv = max(mv, v);
double gx = 0.0, gy = 0.0;
if (d1 > 1e-15) {
gx += vx1 / d1;
gy += vy1 / d1;
}
if (d2 > 1e-15) {
gx += vx2 / d2;
gy += vy2 / d2;
}
double norm2 = gx * gx + gy * gy;
if (norm2 > 1e-18) {
double step = v / norm2;
x -= step * gx;
y -= step * gy;
}
}
}
if (mv <= EPS) break;
}
// Phase 2 fallback: project on the most violated constraint.
if (maxViolation(x, y) > 1e-8) {
for (int it = 0; it < 200000; ++it) {
double bestV = -1.0;
int bestType = -1; // 0=edge, 1=ellipse
int bestIdx = -1;
for (int i = 0; i < (int)edges.size(); ++i) {
const auto &e = edges[i];
double cross = e.dx * (y - e.ay) - e.dy * (x - e.ax);
if (-cross > bestV) {
bestV = -cross;
bestType = 0;
bestIdx = i;
}
}
for (int i = 0; i < (int)ell.size(); ++i) {
const auto &e = ell[i];
double d1 = hypot(x - e.x1, y - e.y1);
double d2 = hypot(x - e.x2, y - e.y2);
double v = d1 + d2 - e.a2;
if (v > bestV) {
bestV = v;
bestType = 1;
bestIdx = i;
}
}
if (bestV <= EPS) break;
if (bestType == 0) {
const auto &e = edges[bestIdx];
double step = bestV / e.norm2;
x -= step * e.gx;
y -= step * e.gy;
} else {
const auto &e = ell[bestIdx];
double vx1 = x - e.x1, vy1 = y - e.y1;
double vx2 = x - e.x2, vy2 = y - e.y2;
double d1 = hypot(vx1, vy1);
double d2 = hypot(vx2, vy2);
double gx = 0.0, gy = 0.0;
if (d1 > 1e-15) {
gx += vx1 / d1;
gy += vy1 / d1;
}
if (d2 > 1e-15) {
gx += vx2 / d2;
gy += vy2 / d2;
}
double norm2 = gx * gx + gy * gy;
if (norm2 > 1e-18) {
double step = bestV / norm2;
x -= step * gx;
y -= step * gy;
}
}
}
}
cout.setf(std::ios::fixed);
cout << setprecision(10) << x << '\n' << setprecision(10) << y << '\n';
return 0;
}
HackerRank Geometry – Good Point