In this HackerEarth Cluster Features problem solution we have given n 2-dimensional data objects or points in a cluster, we can define the centroid (x0,y0) radius R and diameter D.

where R is the average distance from member objects to the centroid, and D is the average pairwise distance within the cluster. Both R and D reflect the tightness of the cluster around the centroid.


HackerEarth Cluster Features problem solution


HackerEarth Cluster Features problem solution.

#include "bits/stdc++.h"

using namespace std;
struct ${$(){ios_base::sync_with_stdio(0);cin.tie(0);}}$;

const int N = 150000 + 5; // Change it
const int MX = 20000 + 5;

int x[N], y[N];
int x_left[N], x_right[N];
int y_down[N], y_up[N];

enum BorderState {
OPEN,
POINT,
CLOSE,
};

struct segmentBorder {
BorderState state;
int y_d, y_u, x, id;
bool operator <(const segmentBorder &s) {
return x < s.x || (x == s.x && state < s.state);
}
};


struct BIT {
int n;
long long LS, SS;

BIT operator +(const BIT& a) const {
return {n + a.n, LS + a.LS, SS + a.SS};
}

BIT operator -(const BIT& a) const {
return {n - a.n, LS - a.LS, SS - a.SS};
}
} B[MX];

BIT ans[2][N];

void update(int idx, int val) {
long long val2 = val * 1LL * val;
while(idx < MX) {
B[idx].n += 1;
B[idx].LS += val;
B[idx].SS += val2;
idx += idx & -idx;
}
}

BIT get(int idx) {
BIT ret = {0, 0LL, 0LL};
while(idx > 0) {
ret.n += B[idx].n;
ret.LS += B[idx].LS;
ret.SS += B[idx].SS;
idx -= idx & -idx;
}
return ret;
}

BIT get(int l, int r) {
return get(r) - get(l - 1);
}

void go(int p, int q, int turn) {

vector <segmentBorder> borders;
for(int i = 0; i < p; i++) {
borders.push_back({POINT, y[i], -1, x[i], -1});
}

for(int i = 0; i < q; i++) {
segmentBorder left_border({OPEN, y_down[i], y_up[i], x_left[i], i});
segmentBorder right_border({CLOSE, y_down[i], y_up[i], x_right[i], i});

borders.push_back(left_border);
borders.push_back(right_border);
}

sort(borders.begin(), borders.end());

for(int i = 0; i < borders.size(); i++) {
if(borders[i].state == POINT) {
update(borders[i].y_d, borders[i].x);
} else if(borders[i].state == OPEN) {
BIT val = get(borders[i].y_d, borders[i].y_u);
ans[turn][borders[i].id] = ans[turn][borders[i].id] - val;
} else if(borders[i].state == CLOSE) {
BIT val = get(borders[i].y_d, borders[i].y_u);
ans[turn][borders[i].id] = ans[turn][borders[i].id] + val;
}
}
}

long long magic(BIT t) {
unsigned long long int ret = t.n * 1ULL * t.SS - t.LS * 1ULL * t.LS;
ret = ret * 3ULL;
ret += t.LS;
return ret;
}

int main() {
int p, q;
scanf("%d %d", &p, &q);

for(int i = 0; i < p; i++)
scanf("%d %d", &x[i], &y[i]);

for(int i = 0; i < q; i++)
scanf("%d %d %d %d", &x_left[i], &x_right[i], &y_down[i], &y_up[i]);

go(p, q, 0);

for(int i = 0; i < p; i++)
swap(x[i], y[i]);

for(int i = 0; i < q; i++) {
swap(x_left[i], y_down[i]);
swap(x_right[i], y_up[i]);
}

memset(B, 0, sizeof(B)); // NOT Required! WHY?

go(p, q, 1);

for(int i = 0; i < q; i++) {
unsigned long long int val = magic(ans[0][i]) + magic(ans[1][i]);
printf("%llu\n", val);
}

return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;

#define ll unsigned long long
#define sd(x) scanf("%d", &(x))
#define pii pair<int, int>
#define F first
#define S second

const int N = 1.5e5 + 10, logN = 15;
const int M = N * logN;
const int MAX = 20005;

struct data{
int n;
ll sumx2, sumy2, sumx, sumy;
data(){n = sumx = sumy = sumx2 = sumy2 = 0;}
data(int x, int y){n = 1, sumx = x, sumx2 = x * x, sumy = y, sumy2 = y * y;}
data operator + (const data & D) const{
data ret;
ret.n = n + D.n;
ret.sumx = sumx + D.sumx;
ret.sumx2 = sumx2 + D.sumx2;
ret.sumy = sumy + D.sumy;
ret.sumy2 = sumy2 + D.sumy2;
return ret;
}
data operator - (const data & D) const{
data ret;
ret.n = n - D.n;
ret.sumx = sumx - D.sumx;
ret.sumx2 = sumx2 - D.sumx2;
ret.sumy = sumy - D.sumy;
ret.sumy2 = sumy2 - D.sumy2;
return ret;
}
} tree[M];

int lft[M], rgt[M], cnt = 0;

data bit[MAX];
void update(int pos, const data & D){
for(; pos < MAX; pos += (pos & (-pos))) bit[pos] = bit[pos] + D;
}

data get(int i){
data ret;
for(; i; i -= (i & -i)) ret = ret + bit[i];
return ret;
}

data get(int l, int r){return get(r) - get(l - 1);}

void insert(int x, int y){
data D = data(x, y);
update(y, D);
}

ll get_ans(data D){
return D.sumx + D.sumy + 3 * (D.n * (D.sumx2 + D.sumy2) - D.sumx * D.sumx - D.sumy * D.sumy);
}

map<pii, data> store[MAX];
vector<pii> queriesY[MAX];
vector<int> pointsY[MAX];

vector<pair<pii, pii>> queries;

data query(int x1, int y1, int x2, int y2){
return store[x2][{y1, y2}] - store[x1 - 1][{y1, y2}];
}

void yes(int x, int y){assert(x >= 1 && x <= 20000 && y >= 1 && y <= 20000);}
int main(){
int p, q;
sd(p); sd(q);
for(int i = 1; i <= p; i++){
int x, y;
sd(x); sd(y);
yes(x, y);
pointsY[x].push_back(y);
}

for(int i = 1; i <= q; i++){
int a, b, c, d;
sd(a); sd(c); sd(b); sd(d);
yes(a, b); yes(c, d);
queries.push_back({{a, b}, {c, d}});
queriesY[a - 1].push_back({b, d});
queriesY[c].push_back({b, d});
}

for(int x = 0; x < MAX; x++){
for(int y : pointsY[x]) insert(x, y);
for(auto y : queriesY[x]) store[x][y] = get(y.F, y.S);
}

for(auto it : queries){
printf("%llu\n", get_ans(query(it.F.F, it.F.S, it.S.F, it.S.S)));
}
}