PROBLEM LINK:
Practice
Contest
Pratik: Setter’s name
Khushi: Tester’s name
Pratik: Editorialist’s name
DIFFICULTY:
EASY-MEDIUM.
PREREQUISITES:
stack, set.
PROBLEM:
You are given a set of coordinates of stations in a city. You have to connect the outermost stations and make a Polygon. Now neglect the points used to make this polygon and again connect the outermost points from the remaining points. Do this until it is not possible to make more polygons from the remaining points. This would make an onion-like structure made of polygons.
The area between every two consecutive polygons is considered as one zone. In this city the multiplier for real estate prices increases as you go to the centre most zone in a Fibonacci series. For example there are a total of N zones in a city (i.e. A,B,C,…N) then zone A has a multiplier of 1x, zone B has multiplier of 1x, zone C has multiplier of 2x and so on.
We will be provided with a base real estate price for the city. With this base price you get the real estate price of each zone by multiplying the base price with the associated multiplier for the zone. We have to find out the average real estate price of the city by taking the average of prices of each zone in the city.
EXPLANATION:
Note: In the above image the the point at (-1,1) is by mistakenly printed as (-2,1)
The outermost polygon(Zone B) will be made by connecting points:
(-2, 2), (0, 2), (2, 2), (2, 0), (1, -2), (0, -2), (-2, 0), (-2, 1)
The next polygon(Zone A) will be made by connecting points:
(1,0), (0, -1), (-1 1)
According to fibonacci series Zone A has multiplier 1 and Zone B also has multiplier 1.
Now,
Real estate price in Zone B = 1 * 500 = 500
Real estate price in Zone A = 1 * 500 = 500
Therefore,
The average price = 500 + 500 / 2 = 500
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long int t;
cin>>t;
while(t–)
{
long long int n,b;
cin>>n>>b;
vectorv;
while(n–)
{
long long int x,y,mx=0;
cin>>x>>y;
mx=max(abs(x),abs(b));
v.push_back(mx);
}
long long int ans=0,count=0;
set<int>s(v.begin(),v.end());
for(auto x:s)
{
cout<<x<<"\n";
}
}
return 0;
}
Tester's Solution
cook your dish here
testCases= int(input());
def createZones(cordinatesList,xCor,yCor):
dup = [];
for m in range(len(cordinatesList)):
if (cordinatesList[m][0]==min(xCor) or cordinatesList[m][0]==max(xCor) or cordinatesList[m][1]==min(yCor) or cordinatesList[m][1]==max(yCor)):
dup.append(m)
return(dup);
for i in range(testCases):
inputs = input().split()
points = int(inputs[0])
price = int(inputs[1])
cordinatesList = []
for j in range(points):
temp = []
res = input().split();
temp.append(int(res[0]))
temp.append(int(res[1]))
cordinatesList.append(temp)
count = 0;
while(len(cordinatesList)>=3):
xCor = []
yCor = []
for cordinateCo in cordinatesList:
xCor.append((cordinateCo[0]))
yCor.append((cordinateCo[1]))
dup = createZones(cordinatesList, xCor, yCor)
dup.reverse()
# print(dup)
count+=1
for element in dup:
cordinatesList.remove(cordinatesList[element])
N = count+1;
n1, n2 = 0, 1
ini = 0
total = 0;
fib = []
if (N==0 or N == 1):
total+=n1*price;
else:
while ini < N:
total+=n1*price;
nth = n1 + n2
n1 = n2
n2 = nth
ini += 1
print(int(total/count))