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;