[Help] Geometry — Local machine giving accurate result for complex query, but not CF :/

Правка en2, от Mooncrater, 2020-03-04 18:06:28

Hello,

I was trying to solve 339 A — Peter and Snow Blower, which basically involves a polygon, bound to some point, by a rope. The polygon moves around the point, in a circle. We have to find the area cleared by the polygon.

Approach: Find the point that is at the maximum distance from the tethering point ($$$P$$$). This is amongst the vertices of the polygon. To find the point, that is closest to $$$P$$$, we consider each side, and find the point on this segment, that is closest to $$$P$$$. A line perpendicular to the segment, that goes through $$$P$$$ is found. The intersection of the segment and the perpendicular is the point closest to $$$P$$$. This point might not be on the segment, so we have to check that too.

Enough explanation. Here is my code. It fails on test 54, which when I run locally, gives out the correct answer.

Good problem.

So, let's think, why this should happen. The -g flag does change the memory. So, if I am accessing some memory that I should not have, then in the local case, that memory is fixed, but not in the case of the online compiler. So, what memory do I access in my code?

const int MAXN = 1e5+5 ;
pt pts[MAXN] ;

And where do I use it?

f(i,0,n)
{
    T a,b ;
    cin>>a>>b ;
    pts[i] = {a,b} ;
    maxd = max(maxd,dist(P,pts[i])) ;
    mind = min(mind,dist(P,pts[i])) ;
}

n is an input, $$$3 \leq n \leq 1e5$$$, so I don't think we have any problem here. Let's see:

f(i,0,n)
{ 
    int j = (i+1)%n ;
    line l ;
    l.v = getv(pts[i],pts[j]) ;
    l.c = cross(l.v,pts[i]) ;
    pt poii = poi(l,P) ;
    if(inseg(pts[i],pts[j],poii))
    {
        mind = min(mind,dist(poii,P)) ;
    }
}

i goes from 0 to n-1. That doesn't cross any barrier. j=(i+1)%n, so j's range is (0,n-1). That too shouldn't do anything bad.

Is there any other place, where I could do a bad memory access?

I think, but no.

Imported functions work different for different compilers?

Whenever I think it's not my fault, I'm 100% wrong. So no.

Where are you little bug. Where do you hide?

I am trying to find this little bug, please share more strategies to find this little pos.

Теги #bug, #geometry

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский Mooncrater 2020-03-04 18:40:09 72 Tiny change: '\nHello,\n\n' -> 'Hello,\n\n'
en2 Английский Mooncrater 2020-03-04 18:06:28 29 Tiny change: 'n\n~~~~~\n\nf(i,0,n)' -> 'n\n~~~~~\nf(i,0,n)'
en1 Английский Mooncrater 2020-03-04 18:04:44 2399 Initial revision (published)