Friday, September 12, 2014

UVa Problem 837 - Light and Transparencies

Problem:

Please find the problem here.

Solution:

This is a hardest nut to crack for me so far. It started with compilation error since I mostly used Visual Studio to develop and some functions does not exist on g++, and yet the function supported in g++ is depreciated in Visual Studio - spending time dealing with stupid trailing zeros as required in the output. Then it comes to bugs in design, ignoring the possibility of negative y coefficient, and also used a stack to represent transparencies which is not necessarily the case...

Enough for whining, let's talk about the actual solution. The basic idea is simple. Sort the x-coordinates, and then walk from negative infinity to positive infinity to get to the transparencies. As mentioned about, the y-coordinates could be negative and need to deal with that by ignoring segments that is completely negative as well as segments that cross the x-axis by cutting into halves and take what we need. Also care has to be taken if some x-coordinates are infinity.

Code:

#include "stdafx.h"
#pragma warning(disable : 4996)

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=10&page=show_problem&problem=778

#include "UVa837.h"

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <stdio.h>

using namespace std;

const unsigned long long raw_positive_infinity = 0x7ff0000000000000;
const unsigned long long raw_negative_infinity = 0xfff0000000000000;
const double positive_infinity = *(double*)&raw_positive_infinity;
const double negative_infinity = *(double*)&raw_negative_infinity;

struct segment_endpoint
{
    double x;
    double transparency;
    bool isEnter;
    int segment_id;
};

bool compare_segment(segment_endpoint* first, segment_endpoint* second)
{
    return first->x < second->x;
}

double to_double(string s)
{
    if (s == "+inf")
    {
        return positive_infinity;
    }
    else if (s == "-inf")
    {
        return negative_infinity;
    }
    else
    {
        double result;
        sscanf(s.c_str(), "%lf", &result);
        return result;
    }
}

string to_my_string(double value)
{
    if (value == positive_infinity)
    {
        return "+inf";
    }
    else if (value == negative_infinity)
    {
        return "-inf";
    }
    else
    {
        char buffer[1024];
        sprintf(buffer, "%#.3f", value);
        return string(buffer);
    }
}

int UVa837()
{
    int number_of_cases;
    cin >> number_of_cases;
    for (int c = 0; c < number_of_cases; c++)
    {
        string s;
        getline(cin, s);
        int number_of_flims;
        cin >> number_of_flims;
        vector<double> segment_transparencies;
        vector<bool> segment_state;
        vector<segment_endpoint*> endpoints;
        int segment_counter = 0;
        for (int i = 0; i < number_of_flims; i++)
        {
            string ix1, iy1, ix2, iy2, ir;
            double x1, y1, x2, y2, r;
            cin >> ix1 >> iy1 >> ix2 >> iy2 >> ir;

            x1 = to_double(ix1);
            y1 = to_double(iy1);
            x2 = to_double(ix2);
            y2 = to_double(iy2);
            r = to_double(ir);

            if (y1 <= 0 && y2 <= 0 && (y1 + y2 < 0))
            {
                // A segment under x-axis can simply be ignored
                continue;
            }

            if (y1 * y2 <= 0)
            {
                if (y1 != 0 || y2 != 0)
                {
                    // A segment crossing (or touching) x-axis
                    // (x2-x1)/(y2-y1) = (cx - x1)/(0 - y1)
                    double cx = x1 - y1 * (x2 - x1) / (y2 - y1);
                    if (y1 <= 0)
                    {
                        x1 = cx;
                        y1 = 0;
                    }
                    else if (y2 <= 0)
                    {
                        x2 = cx;
                        y2 = 0;
                    }
                }
            }

            segment_endpoint* start = new segment_endpoint();
            segment_endpoint* end = new segment_endpoint();
            start->segment_id = segment_counter;
            start->x = min(x1, x2);
            end->segment_id = segment_counter;
            end->x = max(x1, x2);
            start->transparency = r;
            end->transparency = r;
            start->isEnter = true;
            end->isEnter = false;
            endpoints.push_back(start);
            endpoints.push_back(end);
            segment_counter++;
            segment_transparencies.push_back(r);
            segment_state.push_back(false);
        }

        if (endpoints.size() == 0)
        {
            cout << "-inf +inf 1.000";
        }
        else
        {
            sort(endpoints.begin(), endpoints.end(), compare_segment);
            vector<pair<double, double> > results;

            for (vector<segment_endpoint*>::iterator p = endpoints.begin(); p != endpoints.end(); p++)
            {
                segment_endpoint* endpoint = *p;
                if (endpoint->isEnter)
                {
                    segment_state[endpoint->segment_id] = true;
                }
                else
                {
                    segment_state[endpoint->segment_id] = false;
                }

                double current_transparency = 1;
                for (unsigned int i = 0; i < segment_transparencies.size(); i++)
                {
                    if (segment_state[i])
                    {
                        current_transparency *= segment_transparencies[i];
                    }
                }

                results.push_back(pair<double, double>(endpoint->x, current_transparency));
                delete endpoint;
            }

            // results is a list of (x, t), where I expect after x, the transparency is t
            // Now I need t to transform it into segments
            // consider a walk from -inf to +inf
            double current_position = negative_infinity;
            double current_transparency = 1.0;

            int count = results.size();
            if (results.begin()->first == negative_infinity)
            {
                count--;
            }
            if (results.rbegin()->first != positive_infinity)
            {
                count++;
            }
            cout << count << endl;
            int printed = 0;
            for (vector<pair<double, double> >::iterator p = results.begin(); p != results.end(); p++)
            {
                pair<double, double> event_point = *p;
                if (p->first > current_position)
                {
                    cout << to_my_string(current_position) << " " << to_my_string(event_point.first) << " " << to_my_string(current_transparency);
                    current_position = event_point.first;
                    printed++;
                    if (printed != count)
                    {
                        cout << endl;
                    }
                }
                current_transparency = event_point.second;
            }
            if (current_position != positive_infinity)
            {
                cout << to_my_string(current_position) << " " << to_my_string(positive_infinity) << " " << to_my_string(1.0);
            }
        }
        if (c != (number_of_cases - 1))
        {
            cout << endl;
            cout << endl;
        }
    }

    cout << endl;
    return 0;
}

No comments :

Post a Comment