Last Updated on March 28, 2022 by Ria Pathak
CONCEPTS USED:
Computational geometry.
DIFFICULTY LEVEL:
Medium.
PROBLEM STATEMENT(SIMPLIFIED):
For any triangle ABC we know that the height from A to the line BC(or it’s extension) is Ha, from B to the line AC (or it’s extension) is Hb and from C to the line AB (or it’s extension) is Hc. Now you are given these three values and you have to figure out the area of the Triangle ABC.
If the triangle ABC is not possible for the given Ha,Hb,Hc. Print "IMPOSSIBLE".
See original problem statement here
For Example :
Input
4
31.573 22.352 63.448
46.300 50.868 86.683
22.005 24.725 22.914
5.710 25.635 32.805
Output
1517.456
2219.941
311.804
IMPOSSIBLESOLVING APPROACH:
You can find the area of a triangle if you know the length of the three sides by using Heron’s Formula. It seems almost logical that something along the same lines could be used to find the area if you know the three altitudes.
Let the sides of the triangle be a, b, and c. The altitudes to the sides are the heights used to find the area of the triangle. Let the altitudes to sides a, b, and c be called ha, hb, and hc.
The area of the triangle can be found by 1/2 a ha or 1/2 b hb or 1/2 c hc.
a ha = b hb = c hc
a/b = hb/ha
a/c = hc/ha
b/c = hc/hb
Since we know ha, hb, and hc (the altitudes), we will have enough information to find a, b, and c. Then we find the area by Heron’s Formula.
The formula for the area of a triangle in terms of its altitudes is:
A=1/sqrt[(1/ha + 1/hb + 1/hc)*(-1/ha + 1/hb + 1/hc)* (1/ha - 1/hb + 1/hc)*(1/ha + 1/hb - 1/hc) ].where A is the area and ha,hb,hc are the altitudes to sides a,b,c , respectively.
SOLUTIONS:
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define fi first
#define se second
#define pb push_back
///*template{{{
#define sz(x) (ll)x.size()
#define all(x) x.begin(),x.end()
#define trav(a,x) for(auto &a:x)
#define fr(i,a,b) for(ll i=a;i<=b;i++)
#define fr1(i,a) for(ll i=0;i<a;i++)
#define frr(i,a,b) for(ll i=b;i>=a;i--)
#define frr1(i,a) for(ll i=a-1;i>=0;i--)
#define sorta(a,n) sort(a,a+n)
#define sortd(a,n) sort(a,a+n,greater<ll>())
#define sorva(a) sort(a.begin(),a.end())
#define sortvd(a) sort(a.begin(),a.end(),greater<ll>())
#define tc(t) while(t--)
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
using vi= vector<ll>;
using vvi= vector<vi>;
using vb =vector<bool>;
using vc =vector<char>;
using vs =vector<string>;
using vld =vector<ld>;
using pii =pair<ll,ll>;
using psi =pair<string,ll>;
using pci =pair<char,ll>;
using vpii =vector<pii>;
//}}}template*/
ll const mod=998244353;
ll const maxn=1e5+5;
ll const inf=1e18;
ll add(ll a,ll b){
return ((a%mod)+(b%mod))%mod;
}
ll mul(ll a,ll b){
return ((a%mod)*(b%mod))%mod;
}
ll powm(ll x,ll n,ll M)
{
ll result=1;
while(n>0)
{
if(n % 2 ==1)
result=(result * x)%M;
x=(x*x)%M;
n=n/2;
}
return result;
}
ll modinverse(ll a, ll m){
return powm(a,m-2,m);
}
bool prime(ll x){
if(x<=1)return false;
for(int i=2;i<=sqrt(x);i++)if(x%i==0)return false;
return true;
}
ll divisor(ll x){
ll cnt=0;
for(int i=1;i<=sqrt(x);i++){
if(x%i==0){
if(i!=x/i)cnt+=2;
else cnt+=1;
}
}
return cnt;
}
vector<ll> sieve(ll n) {
bool prim[n+1];
memset(prim, true, sizeof(prim));
for (ll p=2; p*p<=n; p++) {
if (prim[p] == true) {
for (int i=p*p; i<=n; i += p)
prim[i] = false;
}
}
vector<ll>v;
for(int i=2;i<=n;i++)if(prim[i])v.push_back(i);
return v;
}
void solve(){
long double ha,hb,hc;
cin>>ha>>hb>>hc;
if(ha<=0 or hb<=0 or hc<=0){
cout<<"IMPOSSIBLE\n";
return ;
}
ha=1.0/ha;
hb=1.0/hb;
hc=1.0/hc;
long double a=(ha+hb+hc);
long double b=(-ha+hb+hc);
long double c=(ha-hb+hc);
long double d=(ha+hb-hc);
if(a<=0 or b<=0 or c<=0 or d<=0){
cout<<"IMPOSSIBLE\n";
return ;
}
a=1.0/a;
b=1.0/b;
c=1.0/c;
d=1.0/d;
a=sqrtl(a);
b=sqrtl(b);
c=sqrtl(c);
d=sqrtl(d);
long double ans=a*b*c*d;
cout<<fixed<<setprecision(3)<<ans<<'\n';
}
int main(){
fio;
ll t;
t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
import java.util.*;
class Heights
{
static Scanner sc=new Scanner(System.in);
static long mod=998244353;
static double maxn=1e5+5;
static double inf=1e18;
long add(long a,long b)
{
return ((a%mod)+(b%mod))%mod;
}
long mul(long a,long b){
return ((a%mod)*(b%mod))%mod;
}
long powm(long x,long n,long M)
{
long result=1;
while(n>0)
{
if(n % 2 ==1)
result=(result * x)%M;
x=(x*x)%M;
n=n/2;
}
return result;
}
long modinverse(long a, long m){
return powm(a,m-2,m);
}
boolean prime(long x){
if(x<=1)return false;
for(int i=2;i<=Math.sqrt(x);i++)if(x%i==0)return false;
return true;
}
long divisor(long x){
long cnt=0;
for(int i=1;i<=Math.sqrt(x);i++){
if(x%i==0){
if(i!=x/i)cnt+=2;
else cnt+=1;
}
}
return cnt;
}
ArrayList<Long> sieve(int n) {
boolean []prim=new boolean[n+1];
Arrays.fill(prim, true);
for (long p=2; p*p<=n; p++) {
if (prim[(int) p] == true) {
for (int i=(int) (p*p); i<=n; i += p)
prim[i] = false;
}
}
ArrayList<Long> v=new ArrayList<>();
for(long i=2;i<=n;i++)
{
if(prim[(int)i]==true)
{
v.add(i);
}
}
return v;
}
static void solve()
{
double ha=sc.nextDouble(),hb=sc.nextDouble(),hc=sc.nextDouble();
if(ha<=0 || hb<=0 || hc<=0)
{
System.out.println("MPOSSIBLE");
return ;
}
ha=1.0/ha;
hb=1.0/hb;
hc=1.0/hc;
double a=(ha+hb+hc);
double b=(-ha+hb+hc);
double c=(ha-hb+hc);
double d=(ha+hb-hc);
if(a<=0 || b<=0 || c<=0 || d<=0)
{
System.out.println("MPOSSIBLE");
return ;
}
a=1.0/a;
b=1.0/b;
c=1.0/c;
d=1.0/d;
a=Math.sqrt(a);
b=Math.sqrt(b);
c=Math.sqrt(c);
d=Math.sqrt(d);
double ans=a*b*c*d;
System.out.println(String.format("%.3f", ans));
}
public static void main(String[] args)
{
long t=sc.nextLong();
while(t!=0)
{
solve();
t--;
}
}
}
[forminator_quiz id="2362"]
This article tried to discuss Computational geometry. Hope this blog helps you understand and solve the problem. To practice more problems on Computational geometry you can check out MYCODE | Competitive Programming.