## 10060 - A hole to catch a man

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

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

### 10060 - A hole to catch a man

I want to ask if there's mistakes in the sample input? It states that the line of input is in the form of T X0 Y0 X1 Y2 ... X0 Y0

However, for the sample input:
2
2 0 0 0 10 5 15 12 10 10 0 0 0
5 0 0 5 100 100 0 0 0
5 3
1
2 0 0 10 0 10 10 0 10
5 2
0
The second last line isn't of this format. Do I understand wrongly? If not, can anyone give the actual sample input data for this case? Thx.

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:
Problem solved. Just to add the first point at the end of the line~

ljb
New poster
Posts: 2
Joined: Wed Oct 09, 2002 10:03 am

### 10060 is there any mistake in the sample input?

the problem say:
Ti X0 Y0 X1 Y1 X2 Y2 &#8230; &#8230; Xn Yn X0 Y0

Where Ti is the thickness of the sheet, and Xi Yi are the coordinates of corner points. The line ends with co-ordinate of the first point.

but the second input does not end with the x0 y0
1
2 0 0 10 0 10 10 0 10 <-should be 0?
5 2

i got wrong answer ,55555555555

cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:
I think that line should be
2 0 0 10 0 10 10 0 10 0 0

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

### 10060 It's frustating

Man, I thought I've got this problem, but it appears that something is wrong...

My approach to solve this problem was summing up all the volumes of the pieces and then dividing by the volume of the man hole. What's wrong?

Thanks, JP!

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
It's likely you rounded off your result, but you must floor() it to get AC.
JongMan @ Yonsei

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm

### 10060

Hi.......really this one is tough any help plz? i m getting WRONG ANSWER. A lot actually

Code: Select all

#include<cstdio>
#include<cmath>
struct point
{
double x,y;
};

point p[10];
int n;

double area(point a,point b,point c)
{
double area;

area=a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
return 0.5*fabs(area);
}

int main()
{
double sum,pt,r,t,total,pi=2*acos(0.0);
int k;
//	freopen("in.in","r",stdin);
while(scanf("%d",&n)==1 && n)
{
total=0;
for(k=0;k<n;k++)
{
scanf("%lf%lf%lf%lf%lf",&pt,&p[0].x,&p[0].y,&p[1].x,&p[1].y);

sum=0;
while(scanf("%lf%lf",&p[2].x,&p[2].y) && (p[2].x!=p[0].x || p[2].y!=p[0].y))
{
sum+=area(p[0],p[1],p[2]);
p[1]=p[2];
}

total+=pt*sum;
}
scanf("%lf%lf",&r,&t);
printf("%.0lf\n",floor(total/(pi*r*r*t)));
}
return 0;
}


Jalal : AIUB SPARKS

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

### hmm

The formula u r using is only acceptable for convex polygon. On the other hand the input polygons may be concave. For concave polygons some or the triangle areas must be negative if you want to get the true result.

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Thank you, Now I have solved this problem and also thanks to my friend Dip who helped me to find the precision error.
Jalal : AIUB SPARKS

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

### 10060

Hello I'm facing problem to understand the problem 10060.Can anybody help me?

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Hi,

The problem is basically this:
Given a volume L1,L2,...,LN and a volume of a man hole MH,
how many times can MH go into L1+L2+...+LN or
answer = floor( (L1+L2+...+LN) / MH );

mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

### 10060 A Hole to Catch a Man WA

Hi

I am getting wa in this problem but don't know why. I have trying to solve
this problem by this equation

Code: Select all


(x1y2 + x2y3 + x3y4 + ............. + xny1) - (y1x2 + y2x3 + y3x4 +.......... ynx1)

can any body help me.

Here is my code

Code: Select all

#include <stdio.h>
#include <string.h>
#include <math.h>

#define pi acos(-1)

char Table[100024];
double x[20005];
double y[20005];

int main() {

int i, j;
int N;

//freopen("D:\\in.txt", "r", stdin);
while (scanf("%d", &N) == 1) {
if (N == 0) break;

gets(Table);
double ans1 = 0, ans2 = 0, ans = 0;
for (j = 1; j <= N; j++) {
gets(Table);

char *p;
p = strtok(Table, " ");
int n = 1;
int m = 1;
double t;
sscanf(p, "%lf", &t);
while (1) {
p = strtok(NULL, " ");
if (p == NULL) break;
sscanf(p, "%lf", &x[n++]);
p = strtok(NULL, " ");
sscanf(p, "%lf", &y[m++]);
}
ans1 = ans2 = 0.0;
for (i = 1; i < n - 1; i++) {
ans1 += ((x[i] * y[i + 1]) - (y[i] * x[i + 1]));
}
ans1 += ((x[n] * y[1]) - (y[n] * x[1]));

ans += fabs(0.5 * (ans1) * t);
}
double area;
double r, s;
scanf("%lf %lf", &r, &s);
area = 1.0 * s * pi * r * r;
printf("%.0lf\n", floor(ans / area + .5));
}
return 0;
}


Thanks
MAP

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
Why are you using gets to take input..

each polygon may be given in more than one line !!

mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)
Sohel

My solution has other problems i have fixed this problem and got
AC.

MAP.

chops
New poster
Posts: 9
Joined: Sat Jan 29, 2005 10:48 pm
Location: dhaka
Contact:
please give me some I/O.