Geometry 1 CodeChef Solution – Queslers

Problem: Geometry 1 CodeChef Solution

You are given a convex polygon with NN sides. You have to answer QQ queries. The ithith query is described by two integers vi,tivi,ti. In this query, all sides of the polygon start moving parallel to their respective perpendicular vector away from the centroid with a constant velocity of viunitssecviunitssec. Output the final area covered by NN sides of the polygon after time titi seconds.

For each query, consider the initial coordinates of vertices of the given polygon.

Note:

  • Since the input-output is large, prefer using fast input-output methods.
  • The problem requires high precision, so prefer using data types with a precision equivalent to long double in C++.

Input Format

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • Each testcase contains N+Q+1N+Q+1 lines of input.
  • The first line of each test case contains two space-separated integers N,QN,Q.
  • NN lines follow. For each valid ii, the ithith of these lines contains two space-separated integers xi,yixi,yi, coordinates of the ithith vertex of the polygon.
  • Next QQ lines follow. For each valid ii, the ithith of these lines contains two space-separated integers vi,tivi,ti, description of the ithith query.

Output Format

For each query, output in a single line the final area covered by NN sides of the polygon.

Your answer will be considered correct if its relative or absolute error does not exceed 10−210−2.

Constraints

  • 1≤T≤2501≤T≤250
  • 3≤N≤1043≤N≤104
  • 1≤Q≤1041≤Q≤104
  • 0≤xi,yi≤2⋅1060≤xi,yi≤2⋅106
  • 1≤vi,ti≤1051≤vi,ti≤105
  • 1≤vi⋅ti≤1051≤vi⋅ti≤105
  • The sum NN over all testcases does not exceed 5⋅1055⋅105.
  • The sum QQ over all testcases does not exceed 5⋅1055⋅105.
  • The vertices of polygon are given in counter-clockwise order.
  • The internal angles of the given polygon are greater than 1∘1∘.

Subtasks

Subtask #1 (100 points): original constraints

Sample Input 1 

2
4 1
1 1
2 1
2 2
1 2
1 1
3 2
1 1
2 1
1 2
1 1
2 3

Sample Output 1 

9.0000000
9.7426406
230.8086578

Explanation

Below are the images for the respective test cases. Inner polygons are the ones at the start and the rays represent the distance traveled by the sides at the given speed in a given time. Outer polygons denote the final ones after the movements of the sides.

Geometry 1 CodeChef Solution Using C++

#include <bits/stdc++.h> 
 
using namespace std; 
 
const int NN = 101010; 
 
using tdouble = double; 
using ldouble = long double; 
 
struct point { 
    int x, y; 
    point(int x = 0, int y = 0) : x(x), y(y) {} 
} p[NN]; 
 
ldouble operator ^ (const point &a, const point &b) {return (ldouble)a.x*b.y - (ldouble)a.y*b.x;} 
point operator - (const point &a, const point &b) {return point(a.x-b.x, a.y-b.y);} 
ldouble nor(const point &a) {return sqrtl((ldouble)a.x*a.x + (ldouble)a.y*a.y);} 
ldouble operator & (const point &a, const point &b) {return acosl(((ldouble)a.x*b.x+(ldouble)a.y*b.y)/nor(a)/nor(b));} 
 
int main() { 
    int T, n, Q; 
    for (cin >> T; T--; ) { 
        scanf("%d%d", &n, &Q); 
        for (int i = 0; i < n; i++) scanf("%d%d", &p[i].x, &p[i].y); 
        ldouble a = 0, b = 0, c = 0; 
        p[n] = p[0]; p[n + 1] = p[1]; 
        for (int i = 0; i < n; i++) { 
            c += p[i] ^ p[i + 1]; 
            b += nor(p[i] - p[i + 1]); 
            a += 1.0 / tanl((p[i] - p[i + 1] & p[i + 2] - p[i + 1]) * 0.5); 
        } 
        c = c * 0.5; 
        int v, t; 
        double x; 
        while (Q--) { 
            scanf("%d%d", &v, &t); 
            x = (ldouble)v * t; 
            printf("%.3lf\n", (tdouble)((a * x + b) * x + c)); 
        } 
    } 
    return 0; 
}

Geometry 1 CodeChef Solution Using C

#include <stdio.h>
#include <math.h>

long double distance(long double x1, long double y1, long double x2, long double y2)
{
    long double sdx = (x2 - x1) * (x2 - x1);
    long double sdy = (y2 - y1) * (y2 - y1);
    return sqrtl(sdx + sdy);
}
int main()
{
    int t;
    scanf("%d", &t);

    while (t--){
        int n, q;
        scanf("%d %d", &n, &q);
        int v[q], t[q];
        long double x[n], y[n];
        for (int i=0; i<n; i++){
            scanf("%Lf %Lf", &x[i], &y[i]);
        } 
        for (int i=0; i<q; i++){
            scanf("%d %d", &v[i], &t[i]);
        }
        long double xfinal[n], yfinal[n];
        for (int i=0; i<n; i++){
            int i1 = i, i2 = (i+1)%n, i3 = (i+2)%n;
            long double len21 = distance(x[i2], y[i2], x[i1], y[i1]);
            long double len32 = distance(x[i3], y[i3], x[i2], y[i2]);
            long double v21[] = {(y[i2]-y[i1])/len21, -(x[i2]-x[i1])/len21};
            long double v32[] = {(y[i3]-y[i2])/len32, -(x[i3]-x[i2])/len32};
            long double A[] = {v21[0], v21[1]};
            long double B[] = {x[i2] - x[i1], y[i2] - y[i1]};
            long double C[] = {v32[0], v32[1]};
            long double D[] = {x[i3] - x[i2], y[i3] - y[i2]};
            long double lamba = ((C[0]-A[0])*D[1] - (C[1]-A[1])*D[0])/(B[0]*D[1]-B[1]*D[0]);
            xfinal[i] = A[0] + lamba*B[0];
            yfinal[i] = A[1] + lamba*B[1];
        }   
        
        long double c1 = 0, c2 = 0, c3 = 0;
        int j = n-1;
        for (int i=0; i<n; i++){
            int i2 = (i+1)%n, j2 = (j+1)%n;
            c1 += (xfinal[i] + xfinal[j])*(yfinal[j] - yfinal[i]);
            c2 += (x[j2] + x[i2])*(yfinal[j] - yfinal[i]) + (y[j2]-y[i2])*(xfinal[i] + xfinal[j]);
            c3 += (x[j2] + x[i2])*(y[j2]-y[i2]);
            j=i;
        }
        c1 = fabs(c1)/2.0;
        c2 = fabs(c2)/2.0;
        c3 = fabs(c3)/2.0;
        for (int l=0; l<q; l++){
            int k = v[l]*t[l];
            printf("%Lf\n", c1*pow(k,2) + c2*k + c3);
        }
    }
    return 0;
}

Geometry 1 CodeChef Solution Using Java

import java.util.*;
import java.io.*;
import java.text.DecimalFormat;
class GEO1{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni(), Q = ni();
        double[][] P = new double[N][];
        double cotTheta = 0, side = 0, init = 0;
        for(int i = 0; i< N; i++)
            P[i] = new double[]{nd(), nd()};
        for(int i = 0; i< N; i++){
            int i1 = (i+N-1)%N, i2 = (i+1)%N;
            double a = dist(P[i], P[i1]), b = dist(P[i], P[i2]), c = dist(P[i1], P[i2]);
            double ang = Math.acos((a*a+b*b-c*c)/(2*a*b))/2;
            cotTheta += 1/Math.tan(ang);
            side += a;
            init += P[i][0]*P[i2][1]-P[i][1]*P[i2][0];
        }
        init /= 2;
        DecimalFormat df = new DecimalFormat("0.00000000");
        for(int q = 0; q< Q; q++){
            double ti = nl()*nl();
            double area = init + side*ti + cotTheta*ti*ti;
            pn(df.format(area));
        }
    }
    double dist(double[] p1, double[] p2){
        return Math.sqrt((p1[0]-p2[0])*(p1[0]-p2[0]) + (p1[1]-p2[1])*(p1[1]-p2[1]));
    }
    double area(double[] p1, double[] p2, double[] p3){
        return 0.5*(p1[0]*(p2[1]-p3[1]) + p2[0]*(p3[1]-p1[1])+p3[0]*(p1[1]-p2[1]));
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new GEO1().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}
Geometry 1 CodeChef Solution Review:

In our experience, we suggest you solve this Geometry 1 CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

Geometry 1 Problem is available on Hacker Rank for Free, if you are stuck anywhere between a compilation, just visit Queslers to get Geometry 1 CodeChef Solution.

Conclusion:

I hope this Geometry 1 CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Hacker Rank, Leetcode, Codechef, Codeforce Solution.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More on Queslers >>

CodeChef Solution

Cognitive Class Answers

Leetcode Solution

Coursera Quiz Answers

Leave a Reply

Your email address will not be published. Required fields are marked *