Page 1 of 1
10088 - Trees on My Island
Posted: Mon Aug 19, 2002 11:11 am
by Even
?? 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
Posted: Tue Sep 10, 2002 2:01 pm
by Yarin
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.
Posted: Sun Nov 10, 2002 3:44 pm
by Shahab
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?
Posted: Wed May 14, 2003 5:11 pm
by the900
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
Test data needed
Posted: Thu Nov 11, 2004 6:10 pm
by d91-lek
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.
More input plz!
Posted: Thu Nov 11, 2004 9:08 pm
by MatteG
Can anyone with AC give my som more input data???
Thx // MatteG
Posted: Fri Nov 12, 2004 11:42 am
by d91-lek
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
Answer:
PS. I have asserted absolute value of all indata is
within 1,000,000.
10088 - Trees on My Island
Posted: Tue Nov 16, 2004 8:20 pm
by Andrey Grigorov
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
ReadLn(N);
While N <> 0 do
Begin
for i:=0 to N-1 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(S-PA/2+1:0:0);
ReadLn(N);
end;
end.
[/pascal]
Posted: Sat Mar 19, 2005 8:54 pm
by czar
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].first-verts[i].first);
dy = abs(verts[j].second-verts[i].second);
tot += gcd(dy,dx);
}
return tot;
}
int main() {
while(read_input(cin))
cout<< (abs(area2())-boundry()+2)/2 <<endl;
return 0;
}
ok
Posted: Thu Apr 28, 2005 8:09 pm
by jaredjohnson
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)
Re: 10088 - Trees on My Island
Posted: Tue May 20, 2008 12:07 pm
by bad_boy
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
Posted: Thu Sep 04, 2008 6:04 pm
by subzero
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....¬¬
???