11017  A Greener World
Moderator: Board moderators
11017  A Greener World
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?
If not, what should be done? sweeping?
And, can I map everything to a normal grid before starting?
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. :)
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. :)

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am
Thanks
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"
"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"
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.
Well, I still like the problem.

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am
Hmm! I actually misunderstood your post... I thought it in a reverse way.kalinov wrote: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.
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 wrote: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!
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?
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?

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Hmm. If you use the formula area = d * d * uarea * sin(theta), where uarea is the polygon area on the unitgrid, 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 inputmy accepted program giveswhile 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
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
Code: Select all
40000000000 1810193359837561600
PS. Sorry Shahriar, but you where the one that tought me to look for extreme and exceptional cases in seemingly simple problems

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am
hmm
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 .
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 .