# HackerEarth Beautiful Badges problem solution

In this HackerEarth Beautiful Badges Assignment problem solution Lucy has got the task to create badges for all students of the school. A badge is created by superimposing two squares. The bottom square should be of blue colour and top square should be of yellow colour. The squares must be rotated in such a way that the projection of the badge displays 8 distinguishable vertices.

`#include <bits/stdc++.h>using namespace std;#define MOD                     1000000007#define pb(x)                   push_back(x)#define mp(x,y)                 make_pair(x,y)#define FF                      first#define SS                      second#define s(n)                    scanf("%d",&n)#define sl(n)                   scanf("%lld",&n)#define sf(n)                   scanf("%lf",&n)#define ss(n)                   scanf("%s",n)#define sc(n)                   {char temp[4]; ss(temp); n=temp[0];}#define LINF                    (long long)1e18#define EPS                     1e-9#define maX(a,b)                ((a)>(b)?(a):(b))#define miN(a,b)                ((a)<(b)?(a):(b))#define abS(x)                  ((x)<0?-(x):(x))typedef long long ll;typedef unsigned long long LL;typedef pair<int,int> PII;typedef pair<LL,LL> PLL;typedef pair<int,PII> TRI;typedef vector<int> VI;typedef vector<LL> VL;typedef vector<ll> vl;typedef vector<PII> VII;typedef vector<TRI> VT;int N, m;PII a[100005];const int MAXN = 2005;int cnt[MAXN], one_st;const int INF = 1000000000; struct edge {  int a, b, cap, flow;}; int n, s, t, d[MAXN], ptr[MAXN], q[MAXN];vector<edge> e;vector<int> g[MAXN]; void add_edge (int a, int b, int cap) {  edge e1 = { a, b, cap, 0 };  edge e2 = { b, a, 0, 0 };  g[a].push_back ((int) e.size());  e.push_back (e1);  g[b].push_back ((int) e.size());  e.push_back (e2);} bool bfs() {  int qh=0, qt=0;  q[qt++] = s;  memset (d, -1, n * sizeof d[0]);  d[s] = 0;  while (qh < qt && d[t] == -1) {    int v = q[qh++];    for (size_t i=0; i<g[v].size(); ++i) {      int id = g[v][i],        to = e[id].b;      if (d[to] == -1 && e[id].flow < e[id].cap) {        q[qt++] = to;        d[to] = d[v] + 1;      }    }  }  return d[t] != -1;} int dfs (int v, int flow) {  if (!flow)  return 0;  if (v == t)  return flow;  for (; ptr[v]<(int)g[v].size(); ++ptr[v]) {    int id = g[v][ptr[v]],      to = e[id].b;    if (d[to] != d[v] + 1)  continue;    int pushed = dfs (to, min (flow, e[id].cap - e[id].flow));    if (pushed) {      e[id].flow += pushed;      e[id^1].flow -= pushed;      return pushed;    }  }  return 0;} int dinic() {  int flow = 0;  for (;;) {    if (!bfs())  break;    memset (ptr, 0, n * sizeof ptr[0]);    while (int pushed = dfs (s, INF))      flow += pushed;  }  return flow;}void precompute() {}void read() {  s(N);  for (int i = 0; i < N; ++i) {    int c_i, d_i;    s(c_i), s(d_i);    a[i] = make_pair(c_i, d_i);  }}void preprocess() {  sort(a, a + N);  int cur = -1;  one_st = -1;  for (int i = 0; i < N; ++i) {    if(i == 0 or (a[i] != a[i - 1])) {      ++cur;      cnt[cur] = 1;    }    else cnt[cur]++;    if(one_st == -1 and a[i].FF == 2) one_st = cur;  }  N = unique(a, a + N) - a;}void solve() {  n = N + 2;;  s = 0, t = N + 1;  for (int i = 0; i < N; ++i) {    if(i < one_st) add_edge(s, i + 1, cnt[i]);    else add_edge(i + 1, t, cnt[i]);  }   for (int i = 0; i < one_st; ++i) {    int mind = ceil(a[i].SS / sqrt(2.0));    int maxd = floor(a[i].SS * sqrt(2.0));    for (int j = one_st; j < N; ++j) {      assert(a[j].FF != a[i].FF);      if(a[j].SS <= maxd and a[j].SS >= mind)         add_edge(i + 1, j + 1, min(cnt[i], cnt[j]));     }       }  cout << dinic();}int main() {    precompute();    read();    preprocess();    solve();    return 0;}`