August Long Challenge Geometry 1 Solution

by

Geometry 1 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.

Also See: August Long Challenge 2021 Solutions

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 absolute error does not exceed 10−210−2.

Constraints

  • 1≤T≤1001≤T≤100
  • 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.

Test case 11:

August Long Challenge Geometry 1 Solution

Test case 22: 1st1st query

August Long Challenge Geometry 1 Solution

Solution

Program C++: Geometry 1 Solution

#include <bits/stdc++.h>
#include <iostream>
#define ull long double
#define ll long long int
using namespace std;
ull area(ull x[],ull y[],ll n) {
	ull leftSum = 0.0;
	ull rightSum = 0.0;
 
	for (ll i = 0; i < n; ++i) {
		ll j = (i + 1) % n;
		leftSum  += x[i] * y[j];
		rightSum += x[j] * y[i];
	}
 
	return 0.5 * abs(leftSum - rightSum);
}
 
ull dist(ull x1,ull y1,ull x2,ull y2){
	return sqrt(((x2-x1)*(x2-x1)) + ((y2-y1)*(y2-y1)));
}
 
void solve(){
	long long int n,q;
    ull ans=0;
    cin>>n>>q;
    ull x[n],y[n],sum_x=0,sum_y=0,A=0;
	cin>>x[0]>>y[0];
	sum_x+=x[0];
	sum_y+=y[0];
	ull perimeter=0,l[n];
    for (ll i = 1; i < n; i++){
        cin>>x[i]>>y[i];
        sum_x+=x[i];
        sum_y+=y[i];
		l[i-1]=dist(x[i],y[i],x[i-1],y[i-1]);
		perimeter+=l[i-1];
    }
	l[n-1]=dist(x[0],y[0],x[n-1],y[n-1]);
	perimeter+=l[n-1];
    ull cross_prod,theta;
	ll j;
	for (ll i = 0; i < n; i++){
		j=i-1;
		if (j < 0) j = n-1;
		cross_prod=((x[i]-x[j])*(x[i]-x[(i+1)%n])) + ((y[i]-y[j])*(y[i]-y[(i+1)%n]));
		theta=acos(cross_prod/(l[i]*l[j]));
		//cout<<theta<<"\n";
		A += (1/tan(theta/2));
	}
	ull v,t,s,original_area=area(x,y,n);
	//cout<<(fixed)<<perimeter<<" "<<A<<" "<<original_area<<"\n";
	for (ll query = 0; query < q; query++){
		cin>>v>>t;
		s=v*t;
		cout<<(fixed)<<((A*s*s) + (perimeter*s) + original_area)<<"\n";
	}
}
 
int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL); 
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

Program Python: Geometry 1 Solution

import math
def distance(p1, p2):
	return math.sqrt((p1[0] - p2[0])*(p1[0] - p2[0]) + (p1[1] - p2[1])*(p1[1] - p2[1]))
def angleWithPoints(p0, p1, p2):
	vec1 = [ p0[0] - p1[0], p0[1] - p1[1] ]
	vec2 = [ p0[0] - p2[0], p0[1] - p2[1] ]
	return math.acos((vec1[0] * vec2[0] + vec1[1] * vec2[1]) / (distance(p0, p1) * distance(p0, p2)))
for _ in range(int(input())):
	size, q = map(int,input().split())
	points = []
	for i in range(size):
		x, y = map(float,input().split())
		points.append([x*1.0 ,y*1.0])
	totalArea = 0.0
	totalPerimeter = 0.0
	delta = 0.0
	for i in range(size):
		prevP = points[(i-1+size) % size]
		currP = points[i]
		nextP = points[(i+1) % size]
		totalArea += currP[0] * nextP[1] - nextP[0] * currP[1]
		totalPerimeter = totalPerimeter + distance(currP, nextP)
		theta = math.pi - angleWithPoints(currP, prevP, nextP)
		delta = delta + math.tan(theta/2.0)
	totalArea = totalArea*0.5
	for i in range(q):
		v, ti = map(float,input().split())
		d = (v*1.0) * (ti*1.0)
		ans = totalArea + (totalPerimeter * d) + (delta * d * d)
		print('%.10f'%ans)

Codechef Long Challenges

August Long Challenge 2021 Solutions

Leave a Comment

twenty − eight =