10088  Trees on My Island
Moderator: Board moderators
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
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
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
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
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 nonconvex
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 roundoff errors
from triangle areas.
My algorithm integrates the polygon area by summing tetraeder
areas formed between the xaxis 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.
I can think of is no problem for my program, but I get WA.
I have tried polygons of both directions and nonconvex
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 roundoff errors
from triangle areas.
My algorithm integrates the polygon area by summing tetraeder
areas formed between the xaxis 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.
More input plz!
Can anyone with AC give my som more input data???
Thx // MatteG
Thx // MatteG
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:
Answer:
PS. I have asserted absolute value of all indata is
within 1,000,000.
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
within 1,000,000.
Last edited by d91lek on Thu Apr 07, 2005 5:21 pm, edited 1 time in total.

 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].YP[(i1) 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.XB.X);
dy:=Abs(A.YB.Y);
if dx < dy then
Begin
min:=dx;
max:=dy;
end
else
Begin
min:=dy;
max:=dx;
end;
if min = 0 then
Result:=max1
else
if max mod min = 0 then
Result:=min1
else
Result:=0;
end;
Begin
ReadLn(N);
While N <> 0 do
Begin
for i:=0 to N1 do
With P do
ReadLn(X,Y);
S:=Square(N);
PA:=N;
for i:=1 to N do
Inc(PA,PointAmount(P,P[(i+1) mod N]));
WriteLn(SPA/2+1:0:0);
ReadLn(N);
end;
end.
[/pascal]
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].YP[(i1) 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.XB.X);
dy:=Abs(A.YB.Y);
if dx < dy then
Begin
min:=dx;
max:=dy;
end
else
Begin
min:=dy;
max:=dx;
end;
if min = 0 then
Result:=max1
else
if max mod min = 0 then
Result:=min1
else
Result:=0;
end;
Begin
ReadLn(N);
While N <> 0 do
Begin
for i:=0 to N1 do
With P do
ReadLn(X,Y);
S:=Square(N);
PA:=N;
for i:=1 to N do
Inc(PA,PointAmount(P,P[(i+1) mod N]));
WriteLn(SPA/2+1:0:0);
ReadLn(N);
end;
end.
[/pascal]
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;
int read_input(istream &cin) {
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;
}
return tot;
}
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].firstverts[i].first);
dy = abs(verts[j].secondverts[i].second);
tot += gcd(dy,dx);
}
return tot;
}
int main() {
while(read_input(cin))
cout<< (abs(area2())boundry()+2)/2 <<endl;
return 0;
}

 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 calculationso don't worry about abs() breaking things in that function)
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!!
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...
when i put the lines:
in the main i got AC....¬¬
???
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].yp[j].x*p[i].y;
dx=p[j].xp[i].x;
dy=p[j].yp[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;
}
Code: Select all
//p=v
for (i=0;i<p.size();i++){
j=(i+1)%n;
dx=p[j].xp[i].x;
dy=p[j].yp[i].y;
pborde+=gcd(abs(dx),abs(dy));
}
???
There is no knowledge that is no power.