GEO1 - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Daanish Mahajan
Tester: Istvan Nagy
Editorialist: Taranpreet Singh

DIFFICULTY

Easy-Medium

PREREQUISITES

Geometry, Trigonometry, Shoelace Formula

PROBLEM

Given a convex polygon with N sides, answer Q queries, where each query is described by integers (v_i, t_i) such that all sides of polygon start moving parallel to their respective perpendicular vector away from the centroid with velocity v_i for t_i seconds, then find the area of the newly formed polygon.

Queries are independent of each other.

QUICK EXPLANATION

  • Divide the newly formed polygon into three categories of regions, one being the original polygon, the other being the region of the rectangles formed by sides of the original polygon, and the last region being the symmetric triangles formed at each vertex.
  • Compute the area of a given polygon using the shoelace formula and the area of the second type region by computing the sum of the length of sides of the given polygon.
  • The area of the third region can be computed by a bit of trigonometry, by drawing perpendicular from vertices to sides of the newly formed polygon.

EXPLANATION

Let’s consider an example first
GEO01

Assume that polygon ABC is the given polygon, and polygon DEF is the polygon formed after the operation is applied, moving each side of polygon d = v_i * t_i units away.

Note that |AL| = |BK| = |BJ| = |CI| = |CH| = |AG| = d and AG \perp AC, CH \perp AC, CI \perp BC, BJ \perp BC, KB \perp AB and AL \perp AB.

We can divide polygon DEF into regions of the following three categories.

  • Polygon ABC
  • Regions sharing a side with polygon ABC (Regions ABKL, BCIJ, and ACHG)
  • Regions only sharing a corner with vertices of ABC (Regions DGA, DLA, EKB, ELB, FHC, FIC)

Region 1

The area of polygon ABC can be computed before all queries using the shoelace formula, or any other formula.

Region 2

These regions are the rectangles formed sharing one side with the original polygon. Regions ABKL, BCIJ, and ACHG are the regions of this type. Since all these are rectangles, the area is length times the breadth.

For region ABDL, the area is |AB|*|AL| = |AB| * d.
For region BCIJ, the area is |BC|*|BJ| = |BC| * d.
For region ACHG, the area is |AC|*|AG| = |AC| * d.

Hence, the total area of all regions of this type is given by d * (|AB| + |BC| + |CA|) which is equal to d times perimeter of the given polygon.

Hence, if we have computed the perimeter of the given polygon beforehand, we can compute the area of all regions of the second category in O(1)

Region 3

Regions DGA, DLA, EKB, EJB, FHC, FIC are the regions in this category, which are all triangles. Moreover, DGA and DLA are symmetric, EJB and EKB are symmetric, and FHC and FIC are symmetric. We want to compute the sum of areas of these regions.

Considering triangle DGA first, we know that GA \perp DG, so this is a right-angled triangle. We also have AC \parallel DF. We also know that DM is the angle bisector of \angle BAC. Let’s assume \angle BAC = \alpha, so \angle MAC = \alpha /2. Since AC \parallel DF, we have \angle ADG = \alpha /2.

We also have |AG| = d. The area of this triangle is given by base * height /2, which is |AG| * |DG| /2 = \frac{d * d * cot(\alpha /2)}{2}

Since DGA and DLA are symmetric, the area of the region DLAG is d^2 * cot(\angle BAC /2). Similarly, we can prove area of region EKBJ as d^2 * cot(\angle ABC /2) and the area of region FHCI as d^2 * cot(\angle ACB /2)

So, the sum of area of regions of this category can be written as d^2 * \displaystyle \sum_{i = 1}^N \cot \left(\frac{\angle V_{i-1} V_i V_{i+1}}{2} \right).

Once again, we can compute \displaystyle \sum_{i = 1}^N \cot \left(\frac{\angle V_{i-1} V_i V_{i+1}}{2} \right) before answering queries.

Lastly, angle between three points can be calculated using cosine rule. Specifically, \angle BAC is given by \displaystyle cos^{-1}\left(\frac{|AB|^2+|AC|^2-|BC|^2}{2*|AB|*|AC|}\right).

Summarizing

Let’s compute X being area of given polygon, S being perimeter of given polygon, and Z = \displaystyle \sum_{i = 1}^N \cot \left(\frac{\angle V_{i-1} V_i V_{i+1}}{2} \right).

The final area is given by formula X + S*d + Z *d*d.

TIME COMPLEXITY

The time complexity is O(N+Q) per test case.

SOLUTIONS

Setter's Solution
# include<bits/stdc++.h>
# define pb push_back 
# define pii pair<int, int>
# define mp make_pair
# define ll long long int
# define pll pair<ll, ll>
# define ld long double 
# define pld pair<ld, ld>
using namespace std;
  
FILE *fp;
ofstream outfile;

const string newln = "\n", space = " ";
const int maxvt = 1e5, minc = 0, maxc = 2e6, maxtn = 5e5, maxtq = 5e5, maxn = 1e4, maxq = 1e4, maxt = 1e2;
ll xc[maxn], yc[maxn];
pll vec(int p1, int p2){
    return {xc[p1] - xc[p2], yc[p1] - yc[p2]};
}
ll cp(pll p1, pll p2){
    return p1.first * p2.second - p1.second * p2.first;
}
ll dp(pll p1, pll p2){
    return p1.first * p2.first + p1.second * p2.second;
}
ld vlen(pll p){
    return sqrt(p.first * p.first + p.second * p.second);
}
bool ang(int x, int n){
    pll p1 = vec((x + 1) % n, x), p2 = vec((x - 1 + n) % n, x);
    ll cross = cp(p1, p2), dot = dp(p1, p2);
    // cout << cross << " " << dot << endl;
    return cross > dot * tan(M_PI / 180);
}
ld hang(int x, int n){
    pll p1 = vec((x + 1) % n, x), p2 = vec((x - 1 + n) % n, x);
    ll dot = dp(p1, p2); 
    ld mul = vlen(p1) * vlen(p2);
    return sqrt((mul + dot) / (mul - dot));   
}
int main()
{   
    // for(int test = 1; test <= 1; test++){
    //     string in = "/home/daanish/CP/codechef/LearningTeam/Problems/geo1/in" + to_string(test) + ".in";
    //     string out = "/home/daanish/CP/codechef/LearningTeam/Problems/geo1/out" + to_string(test) + ".out";
        // freopen(in.c_str(), "r", stdin);
        // freopen(out.c_str(), "w", stdout);
        ios_base::sync_with_stdio(false); cin.tie(NULL);
        int t, n, q, v, tt; cin >> t;
        int sumn = 0, sumq = 0;
        ld mans = 0;
        while(t--){
            cin >> n >> q; sumn += n; sumq += q;
            for(int i = 0; i < n; i++){
                cin >> xc[i] >> yc[i];
            }
            for(int i = 0; i < n; i++){
                assert(ang(i, n));
            }

            ld area = 0;
            for(int i = 0; i < n; i++){
                area += (xc[i] * yc[(i + 1) % n] - yc[i] * xc[(i + 1) % n]);
            }
            area = abs(area) / 2;
            ld hfang = 0, len = 0;
            for(int i = 0; i < n; i++){
                hfang += hang(i, n);
                len += vlen(vec(i, (i + 1) % n));
            }
            // cout << area << " " << hfang << " " << len << endl;
            for(int i = 0; i < q; i++){
                cin >> v >> tt;
                ll vt = v * tt;
                ld ans = vt * (len + vt * hfang) + area;
                mans = max(mans, ans);
                printf("%.9Lf\n", ans);
            }
        }
        // cout << mans << endl;
        assert(sumn <= maxtn); assert(sumq <= maxtq);
    // }
} 
Tester's Solution
#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <random>

#ifdef HOME
    #include <windows.h>
#endif

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }

using namespace std;

struct point2d {
    long double x, y;
    point2d() {}
    point2d(long double x, long double y) : x(x), y(y) {}
    point2d& operator+=(const point2d& t) {
	    x += t.x;
	    y += t.y;
	    return *this;
    }
    point2d& operator-=(const point2d& t) {
	    x -= t.x;
	    y -= t.y;
	    return *this;
    }
    point2d& operator*=(long double t) {
	    x *= t;
	    y *= t;
	    return *this;
    }
    point2d& operator/=(long double t) {
	    x /= t;
	    y /= t;
	    return *this;
    }
    point2d operator+(const point2d& t) const {
	    return point2d(*this) += t;
    }
    point2d operator-(const point2d& t) const {
	    return point2d(*this) -= t;
    }
    point2d operator*(long double t) const {
	    return point2d(*this) *= t;
    }
    point2d operator/(long double t) const {
	    return point2d(*this) /= t;
    }
};

point2d operator*(long double a, point2d b) {
    return b * a;
}

long double area(const vector<point2d>& fig) {
    long double res = 0;
    for (unsigned i = 0; i < fig.size(); i++) {
	    point2d p = i ? fig[i - 1] : fig.back();
	    point2d q = fig[i];
	    res += (p.x - q.x) * (p.y + q.y);
    }
    return fabs(res) / 2;
}

long double dot(point2d a, point2d b) {
    return a.x * b.x + a.y * b.y;
}

long double norm(point2d a) {
    return dot(a, a);
}
long double abs(point2d a) {
    return sqrt(norm(a));
}

long double angle(point2d a, point2d b) {
    return acos(dot(a, b) / abs(a) / abs(b));
}

long double getAngleCos(point2d a, point2d b) {
    return dot(a, b) / abs(a) / abs(b);
}

long double getAngleHalfTanFromCos(long double cosAngle) {
    return sqrt((1 - cosAngle) / (1 + cosAngle));
}

int main(int argc, char** argv) 
{
#ifdef HOME
    if(IsDebuggerPresent())
    {
	    freopen("../in.txt", "rb", stdin);
	    freopen("../out.txt", "wb", stdout);
    }
#endif
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.precision(10);
    cout << fixed;

    int T;
    cin >> T;
    const long double pi = acos(0);
    forn(tc, T)
    {
	    uint32_t N, Q;
	    cin >> N >> Q;
	    vector<point2d> V(N);
	    for (auto& p : V)
	    {
		    uint32_t xx, yy;
		    cin >> xx >> yy;
		    p.x = xx;
		    p.y = yy;
	    }

	    long double ar = area(V);
	    long double sidelen = 0;
	    long double anglelen = 0;

	    forn(i, N)
	    {
		    point2d currSide = V[i] - V[(i + 1) % N];
		    sidelen += abs(currSide);
	    }
	    forn(i, N)
	    {
		    point2d currSide = V[i] - V[(i + 1) % N];
		    point2d nextSide = V[(i + 1) % N] - V[(i + 2) % N];
		    long double cosAngle = getAngleCos(currSide, nextSide);
		    long double currTriangleArea2 = getAngleHalfTanFromCos(cosAngle);
// 			long double currAngle = angle(currSide, nextSide);
// 			long double currTriangleArea = tan((currAngle/2));
		    anglelen += currTriangleArea2;
	    }
		    
	    forn(q, Q)
	    {
		    long double v, t;
		    cin >> v >> t;
		    long double d = v * t;
		    long double res = ar + (sidelen + anglelen * d) * d;
		    printf("%.9Lf\n", res);
	    }

    }
    
    return 0;
}
Editorialist's Solution
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;
        }
    }
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

3 Likes

ratio of 2 similar figures = (ratio of sides)^2 …will this work here?

1 Like

I never got it to work :stuck_out_tongue: I calculated the new side as old side + \frac{X}{\tan{\frac{\alpha}{2}}} + \frac{X}{\tan{\frac{\beta}{2}}}, where \alpha and \beta are the two angles current side is part of. Could anyone elaborate on why this won’t work (passes samples but fails every test)?

https://www.codechef.com/viewsolution/49795370

Here’s where I’m coming from, in case anyone is curious:

We do similar thing for the other angle so the total length is p + \frac{X}{\tan{\frac{\alpha}{2}}} + \frac{X}{\tan{\frac{\beta}{2}}}, so I guess only my math could be wrong.

@nichke for each line increase will be following
X/sin(alpha) + Xtan(90 - alpha) + X/sin(beta) + Xtan(90 - beta)

I don’t think so I tried this for like 10 days but :slightly_frowning_face: it won’t work I don’t know the reason, I thought this was the property of two similar polygons.

Can Someone explain or refer to a proof so as to why → "DM is the angle bisector of \angle∠ BAC. "

Look at my comment above (I provide a proof in the picture). I skipped some steps, but it should be easy to understand with some basic knowledge of geometry.

1 Like

the reason why it won’t work is that the requirements for similarity slightly change when you have more than 4 sides. When that’s the case, just having all angles equal won’t help, you need to have the ratio of adjacent sides to be the same
consider a 5 sided polygon which looks like a hut
now just drag the bottom side downwards

notice that the two polygons have the exact same angles as well, but they are no way similar, and neither is the ratio of their area going to be the square of the ratio of the side length. I made this same mistake which was the reason i couldn’t finish off this question :confused: . i hope this makes sense.

2 Likes

Solution: 49891527 | CodeChef can anybody suggest what’s wrong with my code? it’s passing only 1 test case…

LA and LG are equal since both of them are equal to v*t. Also they share a common hypotenuse, so since they are both right angle triangles with hypotenuse and side length same, therefore they must be congruent. hence DLA is congruent to DLG. meaning that angles DAL and DAG are same.

Can’t it be solved using similar triangles? We first find the centroid of the n sided figure and then arrange the points in cyclic order and then take two vertices in order with the third edge always at the centroid to form the smaller triangle. There is a bigger triangle for every smaller triangle. The bigger and the smaller triangles would be similar, so the area of every bigger triangle can be written in terms of the smaller triangles using the property that the area of two similar triangles is equal to the ratio of squares of their sides and then finally add the area of all the bigger triangles.

After moving each side by say d distance we add extra two red lines to the perimeter where each red line = d * cot(θ/2):

  • i.e. P(x) = P(0) + ∑2* x * cot(θ/2) wher P(x) → perimeter of polygon when sides have moved x distance perpendicularly:

  • Let P = P(0), Q = ∑ 2 * cot(θ/2)
    – P(0)->Sum of initial sides ( O(N) )
    – cot(θ/2) = sqrt ( (1 - cos(θ) ) / ( 1+ cos(θ) ) ) and cos(θ) can be calculated using cosine formula for given sides

  • P(x) = P + Q* x (Note: P and Q are fixed for all queries )

  • A(x) = P(x) * dx ( A(x) → area covered by P(x) perimeter after movind very small dx amount )

  • A = A(x) [0-d] + InitialArea ( get by shoelace formula )

  • A = ( P + Q * x ) * dx [0-d] + InitialArea

  • A = ( P * x + Q * x * x * 0.5) [0-d] + InitialArea

  • A = P * d + Q * d * d * 0.5 + InitialArea

TLDR:

  • Ans = P * d + Q * d * d * 0.5 + initalArea
  • P = InitalPerimeter
  • Q = ∑ 2 * cot(θ/2)

Clean Submission: Solution: 49517165 | CodeChef

it won’t work because this is the property of two similar polygons and it’s not necessary that the final polygon is similar to the initial one, they have the same angles but may not have the same side ratios.
thanks @rudransh_singh

1 Like

It was interesting to find out that the polygons formed near the vertices are “Right Kite”. Right kite - Wikipedia.

d^2 (where d is the offset distance i.e v*t) can be factored out based on the interior angles at each vertex of the initial polygon.
Since the interior angles don’t change as we offset the polygon, the calculation becomes very simple.

1 Like

I have tried by this approach but got WA. Anyone tell whats wrong in this method.

Area of new polygon = Area of old polygon + sum_of_len_of_old_polygon * d + square(d) * [tan(theta1) + tan(theta2) + … + tan(theta_n) ]

Area of old polygon = (1/2 * per1 * len1) + (1/2 * per2 * len2) +…+ (1/2 * per_n * len_n)

MY submission : Solution: 49771068 | CodeChef

@daanish_adm @iscsi @taran_1407

Might be stupid precision error:
Bro you used long double pi = 22.0/7.0; . That would give precision error.
Try changing tan(theta) → cot( (alpha + beta) * 0.5 ). Pi - alpha-beta is too risky in precision

Some obvious problems that I can see are the value of PI. For long double use the high precision variants of tan, sqrt etc. which are tanl, sqrtl. Also, precision errors could be mitigated by calculating by alternative methods like the one suggested by ersshiva. But I just had a brief look so there might be more problems.

I used vectors to calculate angles in the corners. Given unit vectors A and B along successive chords the angle H between them is both arcsin(A x B) and arccos(A . B). For accuracy it is important to use arcsin or arccos of a value not close to 1. The area of the piece in the corner is (offset d squared) * tan(H / 2).

Having passed the first 2 test cases, I spent a long time trying to polish the accuracy for the third test, until I saw that the accuracy of the required results had been relaxed, and I had passed easily. There is no need for ‘long double’.

@ersshiva
This still not working and showing WA
Test have been passed but showing WA on submission

https://www.codechef.com/viewsolution/49908172

can someone tell why my code is giving TLE it O(N+Q)

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define x first
#define y second
#define eb emplace_back
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define fastIO() ios_base::sync_with_stdio, cin.tie(0)
#define pb push_back
#define max(a, b) (a < b ? b : a)
#define min(a, b) (a < b ? a : b)
#define INF 1e9
#define sqrt_2 1.414213562373095048801688724209698078569671875
#define PI 3.14159265358979323846264338327950288419716939937510

ld inital_area, perimeter;
ld summationCotTheta;

inline ld distance(pair<ld, ld> a, pair<ld, ld> b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

int main()
{
    fastIO();
    ll t;
    cin >> t;
    cout << fixed << setprecision(3);
    while (t--)
    {
        ll n, q;

        cin >> n >> q;
        vector<pair<ld, ld>> points(n);
        ld x, y;
        for (auto &p : points)
        {
            cin >> x >> y;
            p.x = x;
            p.y = y;
        }

        perimeter = 0;
        inital_area = 0;
        summationCotTheta = 0;
        for (int i = 0; i < n; i++)
        {
            auto a = points[(i + 1) % n];
            auto b = points[i];
            auto c = points[(i + 2) % n];
            perimeter += distance(b, a);
            inital_area += b.x * a.y - a.x * b.y;
            ld angle = (((b.x - a.x) * (c.x - a.x) + (b.y - a.y) * (c.y - a.y)) / (distance(a, b) * distance(a, c)));
            summationCotTheta += sqrtl((1.0 + angle) / (1.0 - angle));
            // summationCotTheta += abs(1 / tan(angle));
        }
        inital_area /= 2;

        for (int i = 0; i < q; i++)
        {
            ld v, t;
            cin >> v >> t;
            v = v * t;
            ld area = inital_area + v * perimeter + summationCotTheta * v * v;
            cout << area << endl;
        }
    }
}