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

Post by 10153EN » Tue Jun 25, 2002 8:36 pm

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:

Post by 10153EN » Wed Jun 26, 2002 4:10 pm

Problem solved. Just to add the first point at the end of the line~

Thx for reading~

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

10060 is there any mistake in the sample input?

Post by ljb » Thu Oct 10, 2002 5:20 am

the problem say:
Ti X0 Y0 X1 Y1 X2 Y2 … … 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

User avatar
cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:

Post by cytse » Mon Oct 21, 2002 4:55 pm

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

Post by jpfarias » Mon Apr 21, 2003 4:03 am

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:

Post by Whinii F. » Fri Aug 08, 2003 9:37 am

It's likely you rounded off your result, but you must floor() it to get AC. :)
JongMan @ Yonsei

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

10060

Post by CodeMaker » Mon Mar 28, 2005 3:27 pm

Hi.......really this one is tough :-? any help plz? i m getting WRONG ANSWER. :x 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

Post by shahriar_manzoor » Mon Mar 28, 2005 3:56 pm

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.

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Sun Apr 03, 2005 3:01 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

Post by asif_rahman0 » Wed Jun 01, 2005 7:48 pm

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

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Thu Aug 18, 2005 4:32 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 );

User avatar
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

Post by mohiul alam prince » Sun Oct 16, 2005 9:43 am

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

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Sun Oct 23, 2005 3:08 pm

Why are you using gets to take input..

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

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

Post by mohiul alam prince » Sun Oct 23, 2005 3:46 pm

Sohel
Thanks for your reply.

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:

Post by chops » Wed Oct 26, 2005 10:39 pm

please give me some I/O.
Thanks in advance.

Post Reply

Return to “Volume 100 (10000-10099)”