Problem explanation:
Let’s suppose we have a clock that has an hour hand 3 units long, a minute hand 4 units long, and a second hand 5 units long. The hour hand moves once every hour, the minute hand moves once every minute, and the second hand moves once every second. Therefore, exactly every second, the triangle defined by the ends of the hands changes its area.
Which is the maximum area between two given times?
Input: A sequence of hours in sets of 2 in the format hh:mm:ss.
Output: The maximum area defined by the ends of the hands in square units.
For a more comprehensive explanation: https://jutge.org/problems/P17681_en/statement
My code:
I have written a function that takes as arguments the position of the hands in radians and returns its area (trigonometrically intensive).
double area(double secRad, double minRad, double houRad){
double alfaSM = atan( (5-4*cos(abs(secRad-minRad)))/(4*sin(abs(secRad-minRad))) );
double alfaSH = atan( (5-3*cos(abs(secRad-houRad)))/(3*sin(abs(secRad-houRad))) );
double alfaMH = atan( (4-3*cos(abs(minRad-houRad)))/(3*sin(abs(minRad-houRad))) );
double distSM = abs(5*sin(alfaSM)+4*sin(abs(secRad-minRad)-alfaSM));
double distSH = abs(5*sin(alfaSH)+3*sin(abs(secRad-houRad)-alfaSH));
double distMH = abs(4*sin(alfaMH)+3*sin(abs(minRad-houRad)-alfaMH));
double s = (distSM+distSH+distMH)/2;
return s*(s-distSM)*(s-distSH)*(s-distMH);
}
My main function reads the input from the user and calculates the area for each second in the range of time the user has entered, stores the maximum area and finally prints it.
int main(){
char z;
double hI,mI,sI, hF,mF,sF;
while(cin >> hI >> z >> mI >> z >> sI >> hF >> z >> mF >> z >> sF){
double maxArea = 0;
for(int i = 3600*hI+60*mI+sI; i <= 3600*hF+60*mF+sF; i++){
double cacheArea = area( 2*pi*((double)(i%60)/60) , 2*pi*(double)((i%3600)/60)/60, 2*pi*(double)((i%43200)/3600)/12);
if(cacheArea > maxArea) maxArea = cacheArea;
}
cout << fixed << setprecision(3) << sqrt(maxArea) << endl;
}
}
Write this at the beginning so you can test the program:
#include <iostream>
#include <cmath>
#include <iomanip>
#define pi 3.14159265358979323846
using namespace std;
Where am I now and what is left?
The algorithm of the code above works as intended, but it isn't efficient enough. The online judge throws a time limit exceeded error.
I have managed to reduce the number of calculations of area needed by supposing that if the range of time is more than an hour, we just need to check all the combinations for the first hour, since the maximum area will be there and will be appearing again every hour(the relative positions repeat).
I have also implemented a variable that checks if the separation between hands of the clock in the time its checking is smaller than the separation of the hands in the maximum area found until that moment. If it is, the program skips the area calculation.
These changes seem to improve performance considerably (from 43,200 area calculations to ~1,500 in the complete spin of 12 hours), but the judge still doesn't admit it.
I seem to need a cleaner solution, a mathematically prettier one, but I'm struggling to find one.