11017 - A Greener World

[aminallam]

Is there a way to apply pick's theorem?
If not, what should be done? sweeping?
And, can I map everything to a normal grid before starting?

[kalinov]

Yes, Pick's theorem is the key. I used it twice. To count green points and to count green+red points.

But you'll also have to do some scaling, rotating, and shearing. These transformations are "affine" and they preserve collinearity. It's important because that guarantees us that same points will be inside the polygon after the transformation is done.

See http://mathworld.wolfram.com/AffineTransformation.html for more information.

To Mr. Manzoor: Nice problem, I really liked it. :)

[shahriar_manzoor]

Thanks!. But after I give u the following info u migh not like it

"This problem can be solved even without scaling, rotating and shearing, just consider the given grid as a normal grid. So consider the point (-1d,2d) as (-1,2). And find the area. And the acrtual area is easily found from it.

Actually I did not notice it first either. The first version of this problem did not have the area part but stil I used theta and d to confuse people. Kisman's comment was "This is just to make things difficult for the sake of making it difficult" and I agreed with that. So I added the area part just to justify d and theta because I did not want to remove d and theta because then I had to redraw the figures"

[kalinov]

I am aware of everything you said. Actually there is no scaling, rotating or shearing in my program. But there was a lot of that in my mind while I was solving (thinking about) the problem. All calculations are done with integers, except for multiplying area with d*d*sin(theta) in the end.
Well, I still like the problem.

[shahriar_manzoor]

I am aware of everything you said. Actually there is no scaling, rotating or shearing in my program. But there was a lot of that in my mind while I was solving (thinking about) the problem. All calculations are done with integers, except for multiplying area with d*d*sin(theta) in the end.
Well, I still like the problem.

Hmm! I actually misunderstood your post... I thought it in a reverse way.

[aminallam]

I have failed to compute # of green + red points using pick theorem. I have multiplied all xs, ys by 2, then divide result by 2, but this gives only approximation. I need a hint please!

[kalinov]

I have failed to compute # of green + red points using pick theorem. I have multiplied all xs, ys by 2, then divide result by 2, but this gives only approximation. I need a hint please!

What about rotation? :) The reason why you do these transformations is to put a red or green point on *every* point with integer coordinates. Only then you can use Pick's theorem correctly.

[aminallam]

Thank you very much for your co-operation.

[aminallam]

Thanks, now I got the trick, and my output for sample input is correct, but I get WA. I do not use any floating point computations except in computing the area, and this is the part I suspect:

double reqarea = area2*d*d*sin(theta*pi/180.0)/2.0;
cout << nump << " " << setiosflags(ios::fixed) << setprecision(0) << reqarea << endl;
// area2 is the area*2

I tried also rounding with printf(), also I tries adding epsilon.

Please help me, I cannot imagine that the algorithm for such problem is wrong although it runs on sample input, and no double computations included!
Can you provide me with input/output? Is there special cases?

[aminallam]

Solved now. I did mention that I should use long long.
I wonder how someone like me has decided to participate in ACM contests.

[little joey]

Hmm. If you use the formula area = d * d * uarea * sin(theta), where uarea is the polygon area on the unit-grid, the term d * d * uarea can have upto 19 digits ( 0 < d < 10000, and -100000 <= x,y <= 100000, the input description is wrong). This also means that you have to calculate sin(theta) with at least 19 significant digits (probably some more) to get an accurate answer, and that is more than is provided by the double type in C and Pascal.

I see no way out of it, except for using external high accuracy math. Strangely enough I get accepted by using doubles when doing the calculations, while there is no special judge. Does that mean I am lucky to get the same artificial accuracy as the judge solution? Or does the actual input stay within tighter bounds than given in the description.

To illustrate my point: for this input

Code: Select all

8000 45 4
-100000 -100000
-100000 100000
100000 100000
100000 -100000 
0 0 0

my accepted program gives

Code: Select all

40000000000 1810193359837561600

while the true area is obviously 1.28 * sqrt(2) * 10^18, which is rounded to an integer as 1810193359837561662 doing high accuracy math, a difference of 62.

PS. Sorry Shahriar, but you where the one that tought me to look for extreme and exceptional cases in seemingly simple problems

[shahriar_manzoor]

The highest area is

866021073657??

So I guess the judge data is modest and none of the areas are near 0.5 in the decimal part.

PS: I am staying to my old logic, let the smaller errors remain to make the volumes more like the real world contests. Very few contests are error free and contestants need to deal with these things because this is how contests are. And as both Kisman and me did not catch it as a mistake, it should be a common one .