POLYREL - Editorial

PROBLEM LINK:

Practice
Contest
Video Editorial

Setter: Vikas Pandey
Tester: Rahul Dugar
Editorialist: Ishmeet Singh Saggu

DIFFICULTY:

Easy

PREREQUISITES:

Greedy and Geometry

PROBLEM:

Given a strictly convex polygon of N vertices, you have to apply the following operation.

  1. Draw an inner polygon(referred as child polygon in the problem statement) only using the chords of the parent polygon.
  2. Consider the latest drawn inner polygon as parent polygon.

You have to maximize the sum of the number of edges across all drawn polygons.

QUICK EXPLANATION:

  • You don’t need vertices of the polygon to solve the problem. :upside_down_face:
  • First add N to the answer.
  • As we have to maximize the total number of edges we will greedily try to make the largest possible child polygon.
  • The maximum size of the child polygon that we can make is \lfloor \frac{N}{2} \rfloor, where N is the number for vertices in the parent polygon. Add it to the answer. Consider the new child polygon as a parent polygon and continue the process.
  • We will continue this process till the number of vertices in parent polygon is \geq 6.

EXPLANATION:

Keywords:

  • Strictly Convex Polygon - It is a convex polygon in which all interior angles < 180^{\circ}.

Let’s try to solve a simpler problem. Given a strictly convex polygon with N vertices, what is the maximum size of child polygon you can build which will be strictly convex?

For now, assume the construction we are doing gives a strictly convex child polygon I will prove it below why it is strictly convex.

First, consider N is even.

  • Now consider the vertices of the polygon in clockwise order.
  • Start with any random vertex let us refer as 1^{st} vertex. Now think what is the closest next vertex you can choose so that the line joining them doesn’t form the edge? It will be the 3^{rd} vertex in the clockwise order. Now consider this vertex and connect it with the next closest vertex which forms a chord(5^{th} vertex) and soon.
  • Finally you will get a child polygon with vertex 1 - 3 - 5 - ... - (N-1) - 1.
  • The total number of vertices will be \frac{N}{2}.
  • You might ask why it is the largest possible child polygon? It is because if you try to add any more vertex to the construction it will introduce an edge of the parent polygon which makes our construction wrong.

Now when N is odd.

  • We will do the similar construction but one thing to note here is as we build the polygon the last chord which we will add will be between 1 - (N-2) with the gap of two vertexes ( (N-1) and N ).

  • Let us try to work out an example where N is 7, consider vertex in clockwise order. Choose any vertex as 1^{st}. The connection will be made as follows 1 - 3 - 5 - 1.
    Odd_case_png

  • So maximum size of the child polygon is \lfloor \frac{N}{2} \rfloor.

So finally the maximum size of the child polygon which can be formed from a parent polygon of size N is \lfloor \frac{N}{2} \rfloor, and as it depends on N it gives us a hint to use a greedy algorithm to solve this problem which is, At each step, we will try to make the largest possible child polygon which will have a size of \lfloor \frac{N}{2} \rfloor add it to our answer, consider it the new parent polygon and continue the process of making new child polygon until N \geq 6.

Why \geq 6? Because for lower N, the value \lfloor \frac{N}{2} \rfloor \leq 2, and minimum number of sides a polygon can have is 3 (triangle).

Now the only thing left to prove is that the child polygon made by our construction also be strictly convex. For it, it is enough to prove that any two adjacent edges(made up of chords) of the child polygon the angle between them is < 180^{\circ}.

In the figure given below the polygon made with red lines in parent polygon and 2 blue lines represent the adjacent edges of the child polygon. We have to prove \angle B < 180^{\circ}.
Angle_proof_png

  1. \angle A = \angle B + \angle C + \angle D.
  2. \angle A < 180^{\circ}, as parent polygon is strictly convex.
  3. \angle C and \angle D are greater than 0, otherwise chord would have overlapped with the edge of the parent polygon.
  4. All the above condition implies \angle B < 180^{\circ}.

TIME COMPLEXITY:

  • At each step we are reducing N by half. So for each test case, we have to do O(\log{N}) operations.
  • Also we are taking input of the coordinates of the vertex of the polygon require O(N).
  • Total time complexity will be O(S + T*\log{N}). where T is the number of test cases and S is the sum of N over all test cases, where S \leq 2*10^{6}.

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define pb push_back
#define ff first
#define ss second
// #define endl "\n"
 
void solve()
{
    int n, ans=0;
    cin>>n;
    for(int i=0, u, v; i<n; i++)
        cin>>u>>v;
 
    while(n>=3)
        ans+=n, n>>=1;
 
    cout<<ans<<endl;
}
 
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t=1;
    cin>>t;
    while(t--)
        solve();
    return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
 
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
 
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
#define REMOVE_REDUNDANT
typedef double T;
const T EPS = 1e-7;
struct PT {
	T x, y;
	PT() {}
	PT(T x, T y) : x(x), y(y) {}
	bool operator<(const PT &rhs) const { return make_pair(y, x) < make_pair(rhs.y, rhs.x); }
	bool operator==(const PT &rhs) const { return make_pair(y, x) == make_pair(rhs.y, rhs.x); }
};
T cross(PT p, PT q) { return p.x * q.y - p.y * q.x; }
T area2(PT a, PT b, PT c) { return cross(a, b) + cross(b, c) + cross(c, a); }
#ifdef REMOVE_REDUNDANT
bool between(const PT &a, const PT &b, const PT &c) {
	return (fabs(area2(a, b, c)) < EPS && (a.x - b.x) * (c.x - b.x) <= 0 && (a.y - b.y) * (c.y - b.y) <= 0);
}
#endif
void ConvexHull(vector<PT> &pts) {
	sort(all(pts));
	pts.erase(unique(all(pts)), pts.end());
	vector<PT> up, dn;
	fr(i, 0, pts.size() - 1) {
		while (up.size() > 1 && area2(up[up.size() - 2], up.back(), pts[i]) >= 0) up.pop_back();
		while (dn.size() > 1 && area2(dn[dn.size() - 2], dn.back(), pts[i]) <= 0) dn.pop_back();
		up.pb(pts[i]);
		dn.pb(pts[i]);
	}
	pts = dn;
	for (int i = (int)up.size() - 2; i >= 1; i--) pts.pb(up[i]);
 
#ifdef REMOVE_REDUNDANT
	if (pts.size() <= 2) return;
	dn.clear();
	dn.pb(pts[0]);
	dn.pb(pts[1]);
	fr(i, 2, pts.size() - 1) {
		if (between(dn[dn.size() - 2], dn.back(), pts[i])) dn.pop_back();
		dn.pb(pts[i]);
	}
	if (dn.size() >= 3 && between(dn.back(), dn[0], dn[1])) {
		dn[0] = dn.back();
		dn.pop_back();
	}
	pts = dn;
#endif
}
 
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cout<<fixed<<setprecision(8);
	int t=readIntLn(1,1000);
	int sum_n=0;
	while(t--) {
		int n=readIntLn(1,100000);
		sum_n+=n;
		vector<PT> a;
		fr(i,1,n) {
			int x=readIntSp(-1000000000,1000000000);
			int y=readIntLn(-1000000000,1000000000);
			a.pb(PT{x,y});
		}
		ConvexHull(a);
		assert(sz(a)==n);
		int answer=0;
		while(n>2) {
			answer+=n;
			n/=2;
		}
		cout<<answer<<endl;
	}
	assert(1<=sum_n&&sum_n<=2000000);
    assert (getchar() == EOF);
	return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

void solveTestCase() {
	int N; // total number of vertex in initial strictly convex polygon.
	cin >> N;
	vector<int> X(N), Y(N); // X and Y cordinate of the ith vertex.
	for(int i = 0; i < N; i ++) {
		cin >> X[i] >> Y[i];
	}
	long long ans = N; // we have initial N edges.
	while(N >= 6) { // In this loop I am trying to make the largest possible child polygon, given that parent polygon is strictly convex.
		int _N = (N/2); // note that the new child polygon will have floor(N/2) edges and it will also be a strictly convex polygon.
		ans += _N; // adding the total number of edges of the child polygon to the answer.
		N = _N; // making the last drawn polygon as the parent polygon.
	}
	cout << ans << "\n";
}

int main() {
	ios_base::sync_with_stdio(0); // fast IO
	cin.tie(0);
	cout.tie(0);

	int testCase;
	cin >> testCase;
	for(int i = 1; i <= testCase; i ++) {
		solveTestCase();
	}

	return 0;
}

Video Editorial

Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Any suggestions are welcomed. :smile:

4 Likes

Recursive solution

2 Likes

Yes, because clearly as per the question the sides of the child polygon are the chords of the parent polygon.

fjfl

Is this wrong?

If anyone wants video editorial in hind - Link

3 Likes

jo pucha h vo to btade!!

yes , chord means a line joining 2 edges/corners…your fig shows line joining mid points of 2 sides… you are originating it from middle of a side

to bhai parent polygon k to chords hi h, it is joining 2 edges!

chords straight lines hote hain, and question mein diya hai we can not use the sides of a parent polygon as a cord, matlab child polygon ke sides aur parent polygon ke sides same nahi hone chaiye

Chords are formed using vertices only.

1 Like

bhai meri figure dekh , straight lines bhi h, na maine parent polygon ki side use krri h as a cord, matlab child polygon aur parent polygon ke sides same nahi hai…
Dekh ke to bol le

Yaha par mention nhi kiya ki hume parent polygon ke vertices se hi child polygon banana hai, hum apne aap naye vertices banake(inside the parent polygon), unse child polygon bana sakte hai…?

haa thanks bhai, kisine kuch dhang ka reply kia
varna logo ko editorial daalne ki jaldi hoti h bs

cord sirf edge/corner/vertices se nikal/originate kar sakte , kisi line/side ke middle se nahi

App ke figure mein jo chords hain wo ek side ke middle se nikal rahe (chord are like diagonal , joining 2 sides/corners/vertices)

Green lines are cords , app cords koi bhi side se bana sakte(means the traingle formed can be rotated depending on the cords you make)…red line ek side hai…usko cord nahi consider kar sakte

Square mein its not possible as a polygon(closed Figure) can not be formed

please check the picture above,app ka doubt isse sayad clear ho jaega,

Green lines 2 vetices/corner/edge ko join kar rahe. Cord isi ko bolte, 2 lines/sides ko nahi

sides aur edges mai fark btaio bhai

bss yhi nhi pata tha mere ko, bss yhi reh gya tha,
pura code ho gya tha bss ek line daalni thi.
confuse ho gya tha ki edge daalun ya side.

I basically did a DP approach !

3 Likes

Question should have mentioned exactly what a chord of polygon means. I don’t think it is standard term in case of polygons. Pura question vague sa tha aur example tests se bhi samajh nhi aa rha tha. If you see my submissions, I just tried the possibilities.

3 Likes

sides are the white lines, edges are the place(points) where 2 white line meet, also known as vertices

Check this - https://www.quora.com/What-is-the-difference-between-sides-and-edges