## 10088 - Trees on My Island

Moderator: Board moderators

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

### 10088 - Trees on My Island

?? is it possible that input like ...

5
2 2
4 0
4 3
0 1
0 0
0

for this case ... Pick's Theorem A = I + B/2 - 1...
A = 4, I = 9, then B will be 0.5...but should be 1....??

and how to compute A ?

I make CONVEX_HULL and balabala....
but it is slow and get WAWAWAWA... @@

please help .... thank you thank you Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:
That input doesn't look like a simple polygon to me; the polygon will not touch nor intersect itself in this input.

The formula to calculate A can be found in problem 109 in the hint at the bottom. To calculate I, use GCD.

Shahab
New poster
Posts: 24
Joined: Sun Nov 10, 2002 2:17 pm
Excuse me, But I can't understand why do you need the total area of the polygon? I think that there is no clear way to define the number of internal dots having the area of the polygon? the900
New poster
Posts: 3
Joined: Tue Apr 29, 2003 5:03 pm
hello!

I think my program is correct, but when I use the example input:
12
3 1
6 3
9 2
8 4
9 6
9 9
8 9
6 5
5 8
4 4
3 5
1 3

I get 22 points in stead of 21.
With some inputs the output is correct, but with others it is not. I've verified the area and the amount of external points (including the ones that must be added to apply Pick's theorem) and they are correct.
Can anyone help me

d91-lek
New poster
Posts: 22
Joined: Thu Sep 16, 2004 2:25 am
Location: KTH, Stockholm
Contact:

### Test data needed

The two polygons in the spec and all simple polygons
I can think of is no problem for my program, but I get WA.

I have tried polygons of both directions and non-convex
polygons and polygons with origo inside. The only ones
failing are self crossing.

I have tried long int and checking there are max 1000 vertices.

No division until the final calculation to eliminate round-off errors
from triangle areas.

My algorithm integrates the polygon area by summing tetraeder
areas formed between the x-axis and the edges with sign. Simultaneously
it sums gcd(|dx|,|dy|) for the edges giving the number of integer coordinates
covered. Finally Pick's theorem is put to use.

MatteG
New poster
Posts: 3
Joined: Mon Oct 04, 2004 3:39 pm

### More input plz!

Can anyone with AC give my som more input data???
Thx // MatteG

d91-lek
New poster
Posts: 22
Joined: Thu Sep 16, 2004 2:25 am
Location: KTH, Stockholm
Contact:
AC.

long long everywhere did the trick, although its
just the area and border that gets big enough to
need it. Looks like you can't type cast enough or learn
the ways of C's arithmetical casting and truncing
well enough if your name is mine.

Biggest area according to problem statement:

Code: Select all

``````4
-1000000 -1000000
1000000 -1000000
1000000 1000000
-1000000 1000000
``````

Code: Select all

``````3999996000001
``````
PS. I have asserted absolute value of all indata is
within 1,000,000.
Last edited by d91-lek on Thu Apr 07, 2005 5:21 pm, edited 1 time in total.

Andrey Grigorov
New poster
Posts: 8
Joined: Thu Jul 15, 2004 3:52 pm
Location: Russia, Cherepovets

### 10088 - Trees on My Island

Hi!
Can anybody give me some critical test? I don't know why WA. [pascal]
{\$A+,B-,C+,D-,E-,F-,G+,H+,I-,J-,K-,L-,M-,N+,O+,P+,Q-,R-,S-,T-,U-,V+,W-,X+,Y+}
Program Problem10088 (input, output);
{\$APPTYPE CONSOLE}
Type
TPoint = Record
X,Y: Int64;
end;

Var
P: Array [0..1000] of TPoint;
S: Double;
i,PA,N: Integer;

Function Square(N: Integer): Double;
Var
i: Integer;
S: Int64;
Begin
S:=0;
for i:=1 to N do
S:=S+P.X*(P[(i+1) mod N].Y-P[(i-1) mod N].Y);
Result:=Abs(S/2);
end;

Function PointAmount(Const A,B: TPoint): Integer;
Var
dx,dy,min,max: Integer;
Begin
dx:=Abs(A.X-B.X);
dy:=Abs(A.Y-B.Y);
if dx < dy then
Begin
min:=dx;
max:=dy;
end
else
Begin
min:=dy;
max:=dx;
end;
if min = 0 then
Result:=max-1
else
if max mod min = 0 then
Result:=min-1
else
Result:=0;
end;

Begin
While N <> 0 do
Begin
for i:=0 to N-1 do
With P do
S:=Square(N);
PA:=N;
for i:=1 to N do
Inc(PA,PointAmount(P,P[(i+1) mod N]));
WriteLn(S-PA/2+1:0:0);
end;
end.
[/pascal]

czar
New poster
Posts: 15
Joined: Tue Jun 10, 2003 7:30 pm
I have been staring at my code for awhile and I am not sure what is wrong with it. I could use a fresh set(s) of eyes, in finding the error (it is probably a very stupid error) in my code.... or better yet just give me some data that breaks my code. Thanks in advance.

Code: Select all

``````#include<iostream>
#include<vector>
#include<string>

using namespace std;

typedef long long i64;

int nv;
vector<pair<i64,i64> > verts;

i64 x,y;
cin>>nv,cin.ignore();

if(!nv) return 0;

verts = vector<pair<i64,i64> >();

for(int i = 0; i < nv; i++) {

cin>>x>>y,cin.ignore();
verts.push_back(make_pair(x,y));

}

return 1;

}

// returns twice the area
i64 area2() {

i64 tot=0;
int j;

for(int i = 0; i < verts.size(); i++) {

j = (i+1)%verts.size();
tot += verts[i].first*verts[j].second - verts[i].second*verts[j].first;

}

}

i64 gcd(i64 a, i64 b) {

return !b ? a : gcd(b,a%b);

}

//caluclate the boundry points
i64 boundry() {

i64 tot = 0;
i64 dx,dy;

int j;

for(int i = 0; i < verts.size(); i++) {

j = (i+1)%verts.size();
dx = abs(verts[j].first-verts[i].first);
dy = abs(verts[j].second-verts[i].second);

tot += gcd(dy,dx);
}

}

int main() {

cout<< (abs(area2())-boundry()+2)/2 <<endl;

return 0;

}
``````

jaredjohnson
New poster
Posts: 11
Joined: Sun Jan 30, 2005 10:21 pm

### ok

It looks like abs() is breaking your program when you call it on a 64 bit integer. You need to define your own abs() for a 64 bit integer, or have your area2() function return only positive numbers. (You don't need 64 bit integers for the boundary calculation--so don't worry about abs() breaking things in that function)

New poster
Posts: 2
Joined: Thu Apr 03, 2008 5:00 pm

### Re: 10088 - Trees on My Island

Hi there! I wonder, to calculate the number of integer coordinates, we need to cal numbers of divisor of GCD( |dx|, |dy| ) of edges right ? Please help me! I'm having a bug which I don't know how to fix it!!

subzero
New poster
Posts: 26
Joined: Mon Aug 15, 2005 5:21 am

### Re: 10088 - Trees on My Island

bad_boy, yes you need to calculate GCD( |dx|, |dy| )

by the way, I need a little help:

why this code gives me WA...

Code: Select all

``````#include <cstdio>
#include <cmath>
#include <iostream>
#include <vector>
#include <iterator>

using namespace std;

#define type long long

type gcd(type a, type b){
if(b==0) return a;
if(a%b==0 || a==0) return b;
else return gcd(b,a%b);
}

struct point {
type x,y;
};
type pborde;
double area(vector <point> p, int n) {
double total=0;
type dx,dy;
int i,j;
for (i=0;i<p.size();i++){
j=(i+1)%n;
total+=p[i].x*p[j].y-p[j].x*p[i].y;
dx=p[j].x-p[i].x;
dy=p[j].y-p[i].y;

pborde+=gcd(abs(dx),abs(dy));

}
return fabs(total)/2;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("10088.in","r",stdin);
#endif
int n;
vector <point> v;
point dummy;
double a;
while(scanf("%d",&n)==1 && n!=0) {
v.clear();
pborde=0;
while(n--) {
scanf("%lld %lld",&dummy.x,&dummy.y);
v.push_back(dummy);

}
a=area(v,v.size());
printf("%.0lf\n",a-(pborde/2.0)+1);
}
return 0;
}
``````
when i put the lines:

Code: Select all

``````//p=v
for (i=0;i<p.size();i++){
j=(i+1)%n;
dx=p[j].x-p[i].x;
dy=p[j].y-p[i].y;
pborde+=gcd(abs(dx),abs(dy));
}
``````
in the main i got AC....¬¬

???
There is no knowledge that is no power.