10060 - A hole to catch a man

[Diablos]

Please heeeelp, I am trying to solve 10060 a hole to catch a man, and it gives me TLE :S :S :S

I tried to compare the last point with the first point with a very small error Epsilon ( I put 0.0000000000000001 ), and it was then giving WA :S :S :S

please help :S

Code: Select all

#include <iostream>
#include <cstdlib>
#include <cmath>
#include <stdio.h>
#include <climits>
using namespace std;

#ifndef ONLINE_JUDGE
	#include <fstream>
	#define cin in
	ifstream in("10060.in");
#endif

struct point
{
	double  x, y;
	point(){}
	point(double  X, double  Y) : x(X), y(Y) {}
};



int main()
{
	double TotalMass, pi=2*acos(0.0);
	int nPloygon,Thikness;

	cin >> nPloygon;
	while( nPloygon != 0 && cin.good() )
	{
		TotalMass = 0;
		int i;

		for(i=0; i<nPloygon; i++)
		{
			cin>>Thikness;
		
			double A = 0;
			point p0,p_prev, p_curr(INT_MAX,INT_MAX);

			cin>>p0.x>>p0.y;
			p_prev = p0;

			while( p_curr.x != p0.x || p_curr.y != p0.y)
			{
				cin>>p_curr.x>>p_curr.y;
				A +=  p_prev.x * p_curr.y - p_curr.x * p_prev.y;
				p_prev = p_curr ;
			}
			
			TotalMass += fabs( A/2*Thikness );
			
		}
		double R,T;
		cin>>R>>T;

		cout<< (int)(  TotalMass/ ( R*R*T*pi )  )<<endl;
		
		cin >> nPloygon;
	}
	return 0;
}

[abhineet.bansal]

hey guys pls try to solve my problem... i m getting WA ...
i use this formula...

Code: Select all

 Volume1 = sum over all polygons(thickness * 0.5 * (sum over 0<=i<=n-1(mod(xi * y(i+1) - (x(i+1)*y(i)))))
 Volume2 = 22.0/7.0 * r*r*t

 Result = (int)Volume1/Volume2;

pls tell me my mistake...
here is my JAVA code...

Code: Select all

import java.util.*;
import java.io.*;
class Main
{
  public static void main(String args[]) throws IOException
  {
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    while(true)
    {
      int n=Integer.parseInt(br.readLine().trim());
      if(n==0) break;
      double volume=0.0;
      for(int i=0;i<n;i++)
      {
        String inp=br.readLine().trim();
        String arr[]=new String[9000];
        arr=inp.split("\\s+");
        double x1,y1;
        x1=Double.parseDouble(arr[1]);
        y1=Double.parseDouble(arr[2]);
        int k=3;
        double area=0.0;
        while(true)
        {
          double x2,y2;
          x2=Double.parseDouble(arr[k]);
          y2=Double.parseDouble(arr[k+1]);
          area+=(0.5)*((x1*y2)-(x2*y1));
          x1=x2;
          y1=y2;
          if(x1==Double.parseDouble(arr[1]) && y1==Double.parseDouble(arr[2])) break;
          k+=2;
        }
        if(area<0) area*=-1.0;
        volume+=area*(Double.parseDouble(arr[0]));
      }
      String arr[]=new String[2];
      arr=br.readLine().trim().split("\\s+");
      double volume2=22.0*(Double.parseDouble(arr[0]))*(Double.parseDouble(arr[0]))*(Double.parseDouble(arr[1]))/7.0;
      volume/=volume2;
      int ans=(int)volume;
      System.out.println(ans);
    }
  }
}

[kbr_iut]

I used the formula found in the board,, I am getting wrong answer. I need some tricky i/o anyone pliz help me
here is my code.

Code: Select all

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define max 10000

int main(){
	int n,k,flag,N,i,j;
	double sum1,h,x[max],r,y[max],sum,area,pi;
	pi=2*acos(0.0);
	char s[max]="",tem[max]="";
	//freopen("10060.txt","r",stdin);
	while(scanf("%d",&N)==1&&N){
		sum=0.0;
		for(n=0;n<N;n++){
			scanf("%lf",&h);
			gets(s);
			i=0;j=0;
			flag=1;
			while(s[i]!=NULL){
				while(s[i]==' '&&s[i]!=NULL)i++;
				k=0;
				while(s[i]!=' '&&s[i]!=NULL){
					tem[k++]=s[i++];
				}
				tem[k]=NULL;
				if(flag){x[j]=atof(tem);flag=0;}
				else {y[j++]=atof(tem);flag=1;}
				i++;
			}
			sum1=0.0;
			for(i=0;i<j-1;i++){
				sum1+=x[i]*y[i+1]-y[i]*x[i+1];
			}
			sum+=fabs(sum1*.5*h);
		}
		scanf("%lf %lf",&r,&h);
		area=1.0*pi*r*r*h;
		printf("%.0lf\n", floor(sum/area+.5));
	}
	return 0;
}
			

[linux]

I am getting TLE!!

Code: Select all

#include <cstdio>
#include <cmath>
using namespace std;

int main () {
	int N, i, nP, res;
	double thick, x[2000], y[2000], area, sheetVol, manholeVol, mrad, mth;
	
	while (scanf("%d", &N) && N) {
		sheetVol = 0.0;
		while (N--) {
			nP = 0;
			scanf("%lf", &thick);
			scanf("%lf %lf", &x[nP], &y[nP++]);
			
			while (true) {
				scanf("%lf %lf", &x[nP], &y[nP]);
				if (x[nP] == x[0] && y[nP] == y[0]) {
					break;
				}
				nP++;
			}
			area = 0.0;
			for (i=2; i<nP; i++) {
				area += ((x[0] * y[i-1] + x[i-1] * y[i] + x[i] * y[0]) - (y[0] * x[i-1] + y[i-1] * x[i] + y[i] * x[0]));
			}
			sheetVol += area * thick;
		}
		scanf("%lf %lf", &mrad, &mth);
		manholeVol = 2 * acos(0.0) * mrad * mrad * mth;
		sheetVol = fabs(sheetVol) * .5;
		res = (int)(sheetVol / manholeVol);
		printf("%d\n", res);
	}
	
	return 0;
}

[mak(cse_DU)]

I am getting TLE!!

Code: Select all

#include <cstdio>
#include <cmath>
using namespace std;

int main () {
	int N, i, nP, res;
	double thick, x[2000], y[2000], area, sheetVol, manholeVol, mrad, mth;
	
	while (scanf("%d", &N) && N) {
		sheetVol = 0.0;
		while (N--) {
			nP = 0;
			scanf("%lf", &thick);
			scanf("%lf %lf", &x[nP], &y[nP++]);
			
			while (true) {
				scanf("%lf %lf", &x[nP], &y[nP]);
				if (x[nP] == x[0] && y[nP] == y[0]) {
					break;
				}
				nP++;
			}
			area = 0.0;
			for (i=2; i<nP; i++) {
				area += ((x[0] * y[i-1] + x[i-1] * y[i] + x[i] * y[0]) - (y[0] * x[i-1] + y[i-1] * x[i] + y[i] * x[0]));
			}
			sheetVol += area * thick;
		}
		scanf("%lf %lf", &mrad, &mth);
		manholeVol = 2 * acos(0.0) * mrad * mrad * mth;
		sheetVol = fabs(sheetVol) * .5;
		res = (int)(sheetVol / manholeVol);
		printf("%d\n", res);
	}
	
	return 0;
}

See if (x[nP] == x[0] && y[nP] == y[0])

replace it by if( fabs(x[nP]-x[0])<EPS && fabs(y[nP]-y[0])<EPS).
Then you will not get TLE

[linux]

Thanks MAK. It's AC after modifications..

[evernon]

Hi-

I am getting TLE . I have tried all fixes suggested here and it appears to work locally. Help is much appreciated ^^ .

Code: Select all

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

int main(int argc, char ** argv)
{


	while (1)
	{
		int num;
		scanf("%d", &num);
		if (num == 0) break;
		double volume = 0;
		int i;
		for (i = 0; i < num; i++)
		{
			int thickness;
			scanf("%d", &thickness);
			int x[20000];
			int y[20000];
			int x0; int y0;
			scanf("%d", &x0);
			scanf("%d", &y0);
			x[0] = x0;
			y[0] = y0;
			int j = 1;
			while (1)
			{
				int xn;
				int yn;
				scanf("%d", &xn);
				scanf("%d", &yn);
				if (fabs(x0 - xn) < FLT_EPSILON && fabs(y0 - yn) < FLT_EPSILON) break;
				x[j] = xn;
				y[j] = yn;
				j++;
			}
			double area = 0;
			int v;
			for (v = 0; v < j; v++)
			{
				area += x[v - 1] * y[v];
				area -= x[v] * y[v - 1];
			}
			area += x[v] * y[0];
			area -= x[0] * y[v];
			area /= 2.0;
			area = fabs(area);
			volume += area * thickness;
		}
		int radius; int thickness;
		scanf("%d", &radius);
		scanf("%d", &thickness);
		double circleVolume = 3.1415926535 * radius * radius * thickness;
		int amount = floor(volume / circleVolume);
		printf("%d\n", amount);
	}

	return 0;
}

[brianfry713]

I think the input doesn't really have a zero at the end.

replace
scanf("%d", &num);
with
if(scanf("%d", &num)!=1) return 0;