10088 - Trees on My Island

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10088 - Trees on My Island

Post by Even » Mon Aug 19, 2002 11:11 am

?? 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:

Post by Yarin » Tue Sep 10, 2002 2:01 pm

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

Post by Shahab » Sun Nov 10, 2002 3:44 pm

Excuse me, But I can't understand why do you need the total area of the polygon? :roll:

I think that there is no clear way to define the number of internal dots having the area of the polygon? :oops:

the900
New poster
Posts: 3
Joined: Tue Apr 29, 2003 5:03 pm

Post by the900 » Wed May 14, 2003 5:11 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

Post by d91-lek » Thu Nov 11, 2004 6:10 pm

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!

Post by MatteG » Thu Nov 11, 2004 9:08 pm

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:

Post by d91-lek » Fri Nov 12, 2004 11:42 am

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:

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

Post by Andrey Grigorov » Tue Nov 16, 2004 8:20 pm

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]

czar
New poster
Posts: 15
Joined: Tue Jun 10, 2003 7:30 pm

Post by czar » Sat Mar 19, 2005 8:54 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;

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;

}

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

ok

Post by jaredjohnson » Thu Apr 28, 2005 8:09 pm

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)

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

Re: 10088 - Trees on My Island

Post by bad_boy » Tue May 20, 2008 12:07 pm

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

Post by subzero » Thu Sep 04, 2008 6:04 pm

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.

Post Reply

Return to “Volume 100 (10000-10099)”