Author: Priyanshu Damodhare
Tester: Mayuresh Patle
Editorialist: Priyanshu Damodhare
DIFFICULTY:
SIMPLE
PREREQUISITES:
Vectors, Pairs.
PROBLEM:
Given N coordinates on a 2D x-y plane, to find K coordinates closest to the origin(0,0) and calculate sum of all x and y coordinates.
If two points are at same distance, consider the one with smallest x,y co-ordinate sum first.
QUICK EXPLANATION:
Create a vector of pair. First element of pair will be distance from origin i.e. x^2 + y^2, and second element of the pair will be sum of x and y i.e. x+y. Then simply sort the vector and add second element(x+y) of all first K pairs.
EXPLANATION:
This is the simplest and straight forward solution for this problem using some STLs.
First take input of T i.e. Number of testcases
For each testcase, take input of N and K, number of coordinates and number of points to be found respectively.
Now define a vector of pair.
By applying a loop that runs N times, take input of the coordinates i.e x and y and make a pair with first element of pair as the distance from origin(distance from origin is calculated as root(x^2 + y^2)) and second element as the sum of x and y (x+y). Now push this pair in the vector.
After pushing all pairs into the vector, sort the vector.
Now using a loop calculate sum of second element of the pair of first K pairs in the vector.
print the sum
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define fi(asgduyas,n) for(int i=asgduyas;i<n;i++)
#define fj(asgduyas,n) for(int j=asgduyas;j<n;j++)
#define isEven(n) (!(n & 1))
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define pi vector<int,int>
#define all(a) (a).begin(),(a).end()
#define mod 1000000007
#define pmod 998244353
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll l,r,t,n,m;
string s;
cin>>t;
while(t--)
{
ll ans=0;
cin>>n>>m;
vector<pair<ll,ll>> v;
fi(0,n)
{
cin>>l>>r;
v.pb(mp((pow(l,2) + pow(r,2)), l+r) );
}
ll c=0, f=0;
sort(all(v));
for(int i=0; i<m; i++)ans+= v[i].second;
cout<<ans<<"\n";
}
}
Tester's Solution
for _ in range(int(input())):
n,k=map(int,input().split())
l=[]
for _ in range(n):
x,y=map(int,input().split())
l.append(((x*x+y*y)**.5,x+y))
l.sort()
print(sum(map(lambda x:x[1],l[:k])))