Challenge: Elastic rope
Scor cont: 90.0 / 100
Submission status: Wrong Answer
Submission score: 0.9
Submission ID: 464913228
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/elastic-rope/problem
Cerinta
There is an obstacle on a 2D plane in the form of a simple polygon with vertices at points $(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$. Vertex $a$ connects with vertex $b$ via a rope. Each point on the rope is outside the polygon, but the points can be on the boundary. The rope is *elastic*, meaning it always tries to minimize its length and the friction force between the obstacle and the rope is zero. The ends of the rope are fixed at points $(x_a, y_a)$ and $(x_b, y_b)$ and no other point on the rope is fixed.
If the shape of the rope is a line that has never intersects with or overlaps itself, what's the _maximum_ possible length of the rope?Input Format
The first line contains three space-separated integers describing the respective values of $n$, $a$, and $b$.
Each line $i$ of the $n$ subsequent lines contains two space-separated integers denoting the respective values of $x_i$ and $y_i$ corresponding to the polygon's vertices in clockwise or counterclockwise order.Output Format
Print a single floating-point number denoting the maximum possible length of the rope. The answer is considered to be correct if it has an *absolute* error of *at most* $10^{-6}$.
**Sample Input 0**
4 2 4
100 100
200 100
200 200
100 200
**Sample Output 0**
200
**Explanation 0**
In the diagram below, the red line depicts the rope:
**Sample Input 1**
6 4 1
167 84
421 84
283 192
433 298
164 275
320 133
**Sample Output 1**
468.3361845326
**Explanation 1**
In the diagram below, the red line depicts the rope:
Constraints
* $3 \le n \le 500$
* $1 \le x_i, y_i \le 500$
- $1 \le a, b \le n$
- $a \ne b$
- It's guaranteed that the input polygon is simple.Cod sursa
#include <bits/stdc++.h>
using namespace std;
struct Pt { long long x, y; };
static inline __int128 cross(const Pt& o, const Pt& a, const Pt& b) {
return (__int128)(a.x - o.x) * (b.y - o.y) - (__int128)(a.y - o.y) * (b.x - o.x);
}
static inline int sgn(__int128 v){ return (v>0)-(v<0); }
static inline bool properIntersect(const Pt& a, const Pt& b, const Pt& c, const Pt& d) {
int c1 = sgn(cross(a,b,c));
int c2 = sgn(cross(a,b,d));
int c3 = sgn(cross(c,d,a));
int c4 = sgn(cross(c,d,b));
return (c1*c2 < 0) && (c3*c4 < 0);
}
static int pointInPoly(const vector<Pt>& poly, long double x, long double y){
int n = (int)poly.size();
bool inside = false;
const long double EPS = 1e-12L;
for (int i=0,j=n-1;i<n;j=i++){
long double xi = (long double)poly[i].x, yi = (long double)poly[i].y;
long double xj = (long double)poly[j].x, yj = (long double)poly[j].y;
long double cr = (x - xi)*(yj - yi) - (y - yi)*(xj - xi);
long double dot = (x - xi)*(x - xj) + (y - yi)*(y - yj);
if (fabsl(cr) <= EPS && dot <= EPS) return 2;
bool cond = ((yi > y) != (yj > y));
if (cond){
long double xint = xi + (xj - xi)*(y - yi)/(yj - yi);
if (xint > x) inside = !inside;
}
}
return inside ? 1 : 0;
}
static inline bool onSeg(const Pt& a, const Pt& b, const Pt& p){
if (sgn(cross(a,b,p)) != 0) return false;
return min(a.x,b.x) <= p.x && p.x <= max(a.x,b.x) &&
min(a.y,b.y) <= p.y && p.y <= max(a.y,b.y);
}
static bool locallyExterior(const vector<Pt>& poly, int u, const Pt& t){
int n = (int)poly.size();
int up = (u - 1 + n) % n;
int un = (u + 1) % n;
const Pt& U = poly[u];
__int128 c_edge = cross(U, poly[un], poly[up]);
__int128 c_t_n = cross(U, poly[un], t);
__int128 c_t_p = cross(U, poly[up], t);
if (c_edge > 0) {
bool inInterior = (c_t_n > 0) && (c_t_p < 0);
return !inInterior;
}
if (c_edge < 0) {
return (c_t_n <= 0) && (c_t_p >= 0);
}
return c_t_n <= 0;
}
static bool visibleOutside(const vector<Pt>& poly, int u, int v){
if (u == v) return true;
int n = (int)poly.size();
const Pt& A = poly[u];
const Pt& B = poly[v];
// 1) No strict crossing with boundary edges.
for (int i=0;i<n;i++){
int j = (i+1)%n;
if (i==u || i==v || j==u || j==v) continue;
if (properIntersect(A,B,poly[i],poly[j])) return false;
}
// 2) Handle polygon vertices lying on segment AB.
for (int w=0; w<n; ++w) {
if (w==u || w==v) continue;
if (!onSeg(A,B,poly[w])) continue;
int wp = (w - 1 + n) % n;
int wn = (w + 1) % n;
__int128 cp = cross(A,B,poly[wp]);
__int128 cn = cross(A,B,poly[wn]);
__int128 cedge = cross(poly[w], poly[wn], poly[wp]); // >0 convex obstacle vertex
if ((cp > 0 && cn < 0) || (cp < 0 && cn > 0)) return false;
if (cp > 0 && cn > 0 && cedge >= 0) return false;
}
// 3) Local endpoint checks.
if (!locallyExterior(poly, u, B)) return false;
if (!locallyExterior(poly, v, A)) return false;
// 4) Midpoint not strictly inside.
long double mx = ((long double)A.x + (long double)B.x) * 0.5L;
long double my = ((long double)A.y + (long double)B.y) * 0.5L;
if (pointInPoly(poly,mx,my) == 1) return false;
return true;
}
static pair<long double,long double> findInteriorPoint(const vector<Pt>& poly){
int n = (int)poly.size();
long double miny = poly[0].y, maxy = poly[0].y;
for (auto &p: poly){ miny = min(miny,(long double)p.y); maxy = max(maxy,(long double)p.y); }
for (int it=0; it<220; ++it){
long double y = miny + (maxy - miny) * ((long double)it + 0.37L) / 220.73L;
vector<long double> xs;
xs.reserve(n);
for (int i=0;i<n;i++){
int j = (i+1)%n;
long double y1 = poly[i].y, y2 = poly[j].y;
long double x1 = poly[i].x, x2 = poly[j].x;
if ((y1 > y) == (y2 > y)) continue;
long double x = x1 + (x2 - x1) * (y - y1) / (y2 - y1);
xs.push_back(x);
}
sort(xs.begin(), xs.end());
for (int k=0;k+1<(int)xs.size();k+=2){
long double lx = xs[k], rx = xs[k+1];
if (rx - lx > 1e-9L){
long double x = (lx + rx) * 0.5L;
if (pointInPoly(poly,x,y) == 1) return {x,y};
}
}
}
long double x=0,y=0;
for (auto &p: poly){ x += p.x; y += p.y; }
x /= n; y /= n;
if (pointInPoly(poly,x,y) == 1) return {x,y};
return {(long double)poly[0].x + 1e-3L, (long double)poly[0].y + 1e-3L};
}
static vector<int> buildChain(int n, int a, int b, int dir){
vector<int> c;
int i=a;
while(true){
c.push_back(i);
if(i==b) break;
i = (i + dir + n) % n;
}
return c;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,a,b;
cin >> n >> a >> b;
--a; --b;
vector<Pt> poly(n);
for(int i=0;i<n;i++) cin >> poly[i].x >> poly[i].y;
// normalize to CCW for local-exterior logic
__int128 area2 = 0;
for (int i = 0; i < n; ++i) {
int j = (i + 1) % n;
area2 += (__int128)poly[i].x * poly[j].y - (__int128)poly[j].x * poly[i].y;
}
if (area2 < 0) {
reverse(poly.begin(), poly.end());
a = n - 1 - a;
b = n - 1 - b;
}
vector<vector<unsigned char>> vis(n, vector<unsigned char>(n,0));
for(int i=0;i<n;i++){
vis[i][i]=1;
for(int j=i+1;j<n;j++){
unsigned char ok = visibleOutside(poly,i,j)?1:0;
vis[i][j]=vis[j][i]=ok;
}
}
auto inPt = findInteriorPoint(poly);
long double cx = inPt.first, cy = inPt.second;
const long double PI = acosl(-1.0L);
const long double TWO = 2.0L*PI;
vector<long double> th(n);
for(int i=0;i<n;i++) th[i] = atan2l((long double)poly[i].y - cy, (long double)poly[i].x - cx);
vector<vector<signed char>> shift(n, vector<signed char>(n, 0));
for(int u=0;u<n;u++){
for(int v=0;v<n;v++) if (u!=v && vis[u][v]){
long double d = th[v] - th[u];
while (d <= -PI) d += TWO;
while (d > PI) d -= TWO;
long double x = (th[u] + d - th[v]) / TWO;
int m = (int)llround((double)x);
if (m < -3) m = -3;
if (m > 3) m = 3;
shift[u][v] = (signed char)m;
}
}
auto c1 = buildChain(n,a,b,+1);
auto c2 = buildChain(n,a,b,-1);
auto chainShift = [&](const vector<int>& c){
int t=0;
for(int i=0;i+1<(int)c.size();i++) t += (int)shift[c[i]][c[i+1]];
return t;
};
int t1 = chainShift(c1);
int t2 = chainShift(c2);
int Lmin = min(t1,t2) - 4;
int Lmax = max(t1,t2) + 4;
if (!(Lmin <= 0 && 0 <= Lmax)) {
Lmin = min(Lmin, 0);
Lmax = max(Lmax, 0);
}
int L = Lmax - Lmin + 1;
auto idxLayer = [&](int t){ return t - Lmin; };
const long double INF = 1e100L;
vector<vector<long double>> dist(n, vector<long double>(L, INF));
using State = pair<long double, pair<int,int>>;
priority_queue<State, vector<State>, greater<State>> pq;
dist[a][idxLayer(0)] = 0.0L;
pq.push({0.0L, {a, idxLayer(0)}});
while(!pq.empty()){
auto cur = pq.top(); pq.pop();
long double cd = cur.first;
int u = cur.second.first;
int lt = cur.second.second;
if (cd > dist[u][lt] + 1e-18L) continue;
int t = lt + Lmin;
for(int v=0; v<n; v++){
if (!vis[u][v] || u==v) continue;
int nt = t + (int)shift[u][v];
if (nt < Lmin || nt > Lmax) continue;
int nlt = idxLayer(nt);
long double nd = cd + hypotl((long double)poly[u].x - poly[v].x,
(long double)poly[u].y - poly[v].y);
if (nd + 1e-18L < dist[v][nlt]){
dist[v][nlt] = nd;
pq.push({nd,{v,nlt}});
}
}
}
long double d1 = dist[b][idxLayer(t1)];
long double d2 = dist[b][idxLayer(t2)];
long double ans = max(d1,d2);
cout.setf(std::ios::fixed);
cout << setprecision(10) << (double)ans << '\n';
return 0;
}
HackerRank Geometry – Elastic rope