10088 - Trees on My Island

[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

[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.

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

[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

[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.

[MatteG]

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

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

Code: Select all

3999996000001

PS. I have asserted absolute value of all indata is
within 1,000,000.

[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]

[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;

}

[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)

[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!!

[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....¬¬

???