837 - Light and Transparencies

[Karim El Sheikh]

Can someone tell me what is wrong with my java code?
I get all the test cases here right but it gives me Wrong Answer

Code: Select all

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.text.DecimalFormat;
import java.util.Arrays;
import java.util.StringTokenizer;

public class LightAndTransparencies4
{
	public static void main(String[]args) throws IOException
	{
		PrintWriter out = new PrintWriter(System.out);
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	int tests = Integer.parseInt(br.readLine());
    	StringTokenizer st;long[]x1,x2,r,e,v;int nl,i,j,c=0;double y;String x;
    	DecimalFormat dec = new DecimalFormat("0.000");
    	while(tests-->0)
    	{
    		c=0;
    		br.readLine();
    		nl=Integer.parseInt(br.readLine());
    		x1=new long[nl];
    		x2=new long[nl];
    		r=new long[nl];
    		e=new long[(nl-1)*2+3];
    		v=new long[(nl-1)*2+3];
    		for(i=0;i<nl;i++)
    		{
    			st = new StringTokenizer(br.readLine());
    			y=Double.parseDouble(st.nextToken());
    			x1[i]=(long)(y*1000.0);
    			e[c++]=x1[i];
    			st.nextToken();
    			y=Double.parseDouble(st.nextToken());
    			x2[i]=(long)(y*1000.0);
    			e[c++]=x2[i];
    			st.nextToken();
    			if(x2[i]<x1[i])
    			{
    				long temp=x1[i];
    				x1[i]=x2[i];
    				x2[i]=temp;
    			}
    			y=Double.parseDouble(st.nextToken());
    			r[i]=(long)(y*1000.0);
    		}
			//sorting
			for(i=0;i<nl-1;i++)
			{
				for(j=i+1;j<nl;j++)
				{
					if(x1[j]<x1[i])
					{
						long temp1=x1[i],temp2=x2[i],temp3=r[i];
						x1[i]=x1[j];x2[i]=x2[j];r[i]=r[j];
						x1[j]=temp1;x2[j]=temp2;r[j]=temp3;
					}
				}
			}//done sorting
    		e[c]=Long.MAX_VALUE;
    		Arrays.sort(e);
    		v[c]=1000;
    		v[0]=1000;
    		for(i=1;i<c;i++)
    		v[i]=1000;
    		c=1;
    		while (c<e.length-1)
    		{
    			for(i=0;i<nl;i++)
    			{
    				if(e[c]>x1[i]&&e[c]<=x2[i])
    				{
    					v[c]=v[c]*r[i]/1000;
    				}
    			}
    			c++;
    		}
    		out.println(e.length);
    		out.println("-inf "+dec.format(x1[0]/1000.0)+" 1.000");
    		for(i=1;i<e.length-1;i++)
    		{
    			x=dec.format(v[i]/1000.0);
    			out.println(dec.format(e[i-1]/1000.0)+" "+dec.format(e[i]/1000.0)+" "+x);
    		}
    		out.println(dec.format(x2[nl-1]/1000.0)+" +inf 1.000");
    		if(tests!=0)
    		out.println();
    	}
    	out.flush();
	}
}

[brianfry713]

use class Main

[Karim El Sheikh]

I do change the class to Main when I submit

[brianfry713]

I got AC reading the x values as strings. You can safely assume that each x coordinate has exactly one digit after the decimal point.

[Ty4]

I'm getting WA on this, though I've passed all the tests posted so far. Could anyone offer any input?

Code: Select all

#include <cstdio>
#include <set>
#include <vector>

using namespace std;

typedef struct Point{
	float x;
	float y;

	Point() : x(0), y(0) {}
	Point(float _x, float _y) : x(_x), y(_y) {
		if (_x == -0) x = 0;
		if (_y == -0) y = 0;
	}
	Point(const Point &pt) : x(pt.x), y(pt.y) {}

	const bool operator<(const Point & rhs) const
	{
		return x < rhs.x;
	}
} Point;

typedef struct Film{
	float transCoeff;
	pair<Point, Point> endpoints;

	Film(const Point & p1, const Point & p2, float coeff) : transCoeff(coeff)
	{
		if (p2 < p1) endpoints = make_pair(p2, p1);
		else endpoints = make_pair(p1, p2);
	}

	const bool operator<(const Film & rhs) const
	{
		if (rhs.endpoints.first < endpoints.first) return false;
		return endpoints.second < rhs.endpoints.second;
	}

} Film;

int main()
{
	int cases;
	scanf("%d", &cases);

	while (cases-- > 0){
		int NL;
		set<Film> filmSet;
		set<Point> endpointSet;
		vector<Film> filmArray;
		vector<Point> pointArray;

		scanf("%d", &NL);
		while (NL-- > 0){
			float x1, y1, x2, y2, r;
			scanf("%f %f %f %f %f", &x1, &y1, &x2, &y2, &r);
			endpointSet.insert(Point(x1, y1));
			endpointSet.insert(Point(x2, y2));
			filmSet.insert(Film(Point(x1, y1), Point(x2, y2), r));
		}

		for (set<Film>::iterator it = filmSet.begin(); it != filmSet.end(); ++it)
			filmArray.push_back(*it);
		for (set<Point>::iterator it = endpointSet.begin(); it != endpointSet.end(); ++it)
			pointArray.push_back(*it);

		printf("%d\n", pointArray.size()+1);
		printf("-inf %.3f 1.000\n", pointArray[0].x);
		for (int i = 1; i < pointArray.size(); ++i){
			float result = 1.0;

			for (int j = 0; j < filmArray.size(); ++j){
				Point p1 = filmArray[j].endpoints.first;
				Point p2 = filmArray[j].endpoints.second;
				if ((p1.x <= pointArray[i-1].x) && (p2.x >= pointArray[i].x))
					result *= filmArray[j].transCoeff;
			}
			printf("%.3f %.3f %.3f\n", pointArray[i-1].x, pointArray[i].x, result);
			if (i == pointArray.size()-1)
				printf("%.3f +inf 1.000\n", pointArray[i].x);
		}
		if (cases)
			printf("\n");
	}

	return 0;
}

[brianfry713]

I got AC reading the x values as strings. You can safely assume that each x coordinate has exactly one digit after the decimal point.
Also use double instead of float.

[chenqian]

Hello everyone I have tested all the test case posted in the forum but I still have a wrong answer. Anyone have time to help me? Thanks a lot!!! This is my code.

Code: Select all

deleted after get accepted

[lighted]

Your code i accepted code. But PE

Remove extra space in this line

Code: Select all

printf("%.3lf %.3lf  %.3lf\n", aux,it->first,it->second);

Don't forget to remove your code after getting accepted.

[chenqian]

Thanks a lot, it was very strange. it's necessary to have a "\n" at the last line. without the "\n" it's a wrong answer....

[brianfry713]

Don't ever count on getting PE, missing or extra newline chars will usually result in WA.

[lennart1997]

Can someone tell my why I get a WA?

Code: Select all

import java.io.IOException;
import java.util.*;
import java.util.Locale;

public class Main
{
    public int d;
    static String ReadLn (int maxLg)  // utility function to read from stdin
    {
        byte lin[] = new byte [maxLg];
        int lg = 0, car = -1;
        String line = "";
        

        try
        {
            while (lg < maxLg)
            {
                car = System.in.read();
                if ((car < 0) || (car == '\n')) break;
                lin [lg++] += car;
            }
        }
        catch (IOException e)
        {
            return (null);
        }

        if ((car < 0) && (lg == 0)) return (null);  // eof
        return (new String (lin, 0, lg));
    }

    public static void main (String args[])  // entry point from OS
    {
        Main myWork = new Main();  // create a dinamic instance
        myWork.Begin();            // the true entry point
    }

    void Begin()
    {
        String s;
        boolean fLoop =true;

        s=ReadLn(1024);
        StringTokenizer strTok = new StringTokenizer(s);
        int idxCase = Integer.parseInt( strTok.nextToken() );
        int idx=0;
        d=idxCase;

        while( fLoop ) {

            if(idx==idxCase )
            {

                fLoop = false;
            }
            else{
                s=ReadLn(1024);
                s=ReadLn(1024);
                StringTokenizer strTo = new StringTokenizer(s);
                int np = Integer.parseInt( strTo.nextToken() );

                

                solveTestCase( np,idx);
                
                if((idx+1)!=idxCase)
                {
                    System.out.println();
                }
                idx++;
            }
        }
    }

    public void solveTestCase(int np, int x)
    {
        double [] x1 = new double [np];
        double [] y1 = new double [np];
        double [] x2 = new double [np];
        double [] y2 = new double [np];
        double [] r = new double [np];
        double [] xaus = new double [(np-1)*2+2];
        double [] raus = new double [(np-1)*2+2];

        for(int i=0;i<np;i++)
        {
            String s=ReadLn(1024);
            StringTokenizer strTok = new StringTokenizer(s);
            x1[i] = Double.parseDouble( strTok.nextToken() );
            y1[i] = Double.parseDouble( strTok.nextToken() );
            x2[i] = Double.parseDouble( strTok.nextToken() );
            y2[i] = Double.parseDouble( strTok.nextToken() );
            r[i] = Double.parseDouble( strTok.nextToken() );

        }
                for(int a=1;a<np;a++)
        {
        for(int i=x1.length-1;i>0;i--)
        {
            if(x1[i]<x1[i-1])
            {
                double temp=x1[i-1];
                x1[i-1]=x1[i];
                x1[i]=temp;
                temp=x2[i-1];
                x2[i-1]=x2[i];
                x2[i]=temp;
                temp=r[i-1];
                r[i-1]=r[i];
                r[i]=temp;
            }
        }
       }
                       for(int i=0;i<np;i++)
        {
            if(x2[i]<x1[i])
            {
                double temp=x1[i];
                x1[i]=x2[i];
                x2[i]=temp;
            }

        }
        for(int i=0;i<np;i++)
        {
            xaus[i]=x1[i];
        }


        int h=0;
        for(int i=np;i<xaus.length;i++)
        {
            xaus[i]=x2[h];
            h++;
        }
            
        
        

         for(int a=1;a<(np-1)*2+2;a++)
        {
        for(int i=(np-1)*2+1;i>0;i--)
        {
            if(xaus[i]<xaus[i-1])
            {
                double temp=xaus[i-1];
                xaus[i-1]=xaus[i];
                xaus[i]=temp;

            }
        }
       }

        int c=1;
        if(np!=0)
        {
        raus[0]=1.000;
        while (c<xaus.length)
        {
            for(int i=0;i<np;i++)
              {
                if(xaus[c]>x1[i]&&xaus[c]<=x2[i]&&raus[c]==0)
                {
                    raus[c]=r[i];
                }
                else if(xaus[c]>x1[i]&&xaus[c]<=x2[i]&&xaus[c]>xaus[c-1])
                {
                    raus[c]=raus[c]*r[i];
                }

            }
            c++;
        }
       }
        
        if(np==0)
        {
            System.out.println("1");
            System.out.format(Locale.US,"-inf +inf 1.000%n");
        }
        else{
            System.out.println((np-1)*2+3);
            
        System.out.format(Locale.US,"-inf %.3f %.3f%n",xaus[0],raus[0]);
        
        for(int i=0;i<xaus.length-1;i++)
        {
             System.out.format(Locale.US,"%.3f %.3f %.3f%n",xaus[i],xaus[i+1],raus[i+1]);
        }
        if(x!=d-1)
        {
         System.out.format(Locale.US,"%.3f +inf %.3f%n",xaus[xaus.length-1],raus[0]);
        }
        else{
            System.out.format(Locale.US,"%.3f +inf %.3f",xaus[xaus.length-1],raus[0]);
        }
       }
     }
    
}