Hello, I am trying to solve this problem on SPOJ, where is given a set of red lines and blue lines and you have to count the red/blue intersections. My code uses line sweep technique. Initially I was getting a TLE, then I started to use this set. Now I am getting WA veredict.

My idea is: I create 3 kinds of events: — 0 — x of a start of horizontal line — 1 — x of a vertical line — 2 — x of a end of horizontal line then I sort the events, maintaining a set of active horizontal lines (their y's). When I get to a type 1 event (vertical line) I add to the answer the number of horizontal lines in the active set that are intersecting with the vertical line.

Can anybody tell if it's my idea or my implementation and give me some light please :D Thanks!

Hello guys!

I was solving a contest on gym here at codeforces and I faced this problem where basically you have to calculate the area of a quadrilateral given by four points in a 2D plane.

In contest time I solved the problem identifying the point that makes the polygon not convex (if there is one), since there's no guarantee of it being convex, and from it I form 2 triangles, so the area is the sum of this 2 triangles areas. The code is messy but you can see it here.

After the contest I went to look for other people solutions and most of them seem to have solved using determinant, but not for calculate the area of the 2 triangles like me, it's like given the four points of the quadrilateral a, b, c and d, the area is 1/2 * (det(a,b) + det(b,c) + det(c,d) + det(d,a)), but I have no idea why this is true.

If someone can explain this relation, or point me to some place that explains it I would be very thankfull! :D

The problem I'm talking about is this one http://codeforces.net/gym/100733/problem/J, where you have a set of objects and a set of line segments and you want to maximize the number of objects that have at least one segment above and below itself, by just moving the segments horizontally, and the segments and objects never share the same y coordinate (see the problem for a clearer explanation), initially I thought to simulate moving the objects in steps of 1 on x axis so I would try all possible configurations, but once I read that the x and y coordinates may vary from 0 to 10^6, it would be a TLE answer since I can have 10^3 objects, I've seen a problem similar to this one before and couldn't solve, now again. Can someone help me to understand how to get a AC answer on this kind of problem?

Thanks!!