Land Use, Zoning & Location Optimization Projects

// Weighted median (1D) - O(n log n)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
  int n;
  if(!(cin>>n)) return 0;
  vector> a(n);
  ll total=0;
  for(int i=0;i<n;i++){ cin>>a[i].first>>a[i].second; total+=a[i].second; }
  sort(a.begin(), a.end());
  ll acc=0, half=(total+1)/2, median=a.back().first;
  for(auto &p:a){ acc+=p.second; if(acc>=half){ median=p.first; break; } }
  ll cost=0; for(auto &p:a) cost += llabs(p.first - median) * p.second;
  cout << median << " " << cost << "\\n";
  return 0;
}

// Dijkstra distances + greedy assignment
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (1LL<<60);
vector dijkstra(int src, const vector>> &g){
  int n=g.size(); vector dist(n, INF);
  dist[src]=0; priority_queue, vector>, greater>> pq; pq.push({0,src});
  while(!pq.empty()){
    auto [d,u]=pq.top(); pq.pop(); if(d!=dist[u]) continue;
    for(auto &e:g[u]){ int v=e.first; ll w=e.second; if(dist[v] > d + w){ dist[v]=d + w; pq.push({dist[v], v}); } }
  }
  return dist;
}
int main(){ ios::sync_with_stdio(false); cin.tie(nullptr);
  int n,m; cin>>n>>m; vector>> g(n);
  for(int i=0;i<m;i++){ int u,v,w; cin>>u>>v>>w; g[u].push_back({v,w}); g[v].push_back({u,w}); }
  int S; cin>>S; vector students(S); for(int i=0;i<S;i++) cin>>students[i];
  int K; cin>>K; vector schools(K), cap(K); for(int i=0;i<K;i++) cin>>schools[i]>>cap[i];
  vector> distFromSchool(K, vector(n, INF));
  for(int i=0;i<K;i++) distFromSchool[i] = dijkstra(schools[i], g);
  using T=tuple; priority_queue, greater> pq;
  for(int si=0; si<S; ++si) for(int ki=0; ki<K; ++ki) if(distFromSchool[ki][students[si]] assigned(S,-1); ll total=0;
  while(!pq.empty()){
    auto [d,si,ki]=pq.top(); pq.pop();
    if(assigned[si]!=-1) continue;
    if(cap[ki]<=0) continue;
    assigned[si]=ki; cap[ki]--; total+=d;
  }
  for(int i=0;i<S;i++) cout << i << " -> " << (assigned[i]==-1? -1: schools[assigned[i]]) << "\\n";
  cout << "Total cost: " << total << "\\n";
  return 0;
}

// Greedy assignment with permit prefix matching
#include <bits/stdc++.h>
using namespace std;
struct Trie{ unordered_map<char,Trie*> ch; bool end=false; void ins(const string&s){ Trie*cur=this; for(char c:s){ if(!cur->ch[c]) cur->ch[c]=new Trie(); cur=cur->ch[c]; } cur->end=true; } bool starts(const string&p){ Trie*cur=this; for(char c:p){ if(!cur->ch[c]) return false; cur=cur->ch[c]; } return true; } };
int main(){ ios::sync_with_stdio(false); cin.tie(nullptr);
  int C,S; cin>>C>>S; struct Car{int x,y; string p;}; vector<Car> cars(C);
  for(int i=0;i<C;i++) cin>>cars[i].x>>cars[i].y>>cars[i].p;
  struct Slot{int x,y; string r;}; vector<Slot> slots(S);
  Trie root;
  for(int i=0;i<S;i++){ cin>>slots[i].x>>slots[i].y>>slots[i].r; if(slots[i].r!="-") root.ins(slots[i].r); }
  struct T{int car,slot; double d;};
  vector<T> v;
  auto dist=[&](int x1,int y1,int x2,int y2){ return hypot(x1-x2,y1-y2); };
  for(int i=0;i<C;i++) for(int j=0;j<S;j++){
    if(slots[j].r=="-" || cars[i].p.rfind(slots[j].r,0)==0) v.push_back({i,j,dist(cars[i].x,cars[i].y,slots[j].x,slots[j].y)});
  }
  sort(v.begin(), v.end(), [](auto&a,auto&b){ return a.d carUsed(C,-1), slotUsed(S,-1); double total=0;
  for(auto &t:v) if(carUsed[t.car]==-1 && slotUsed[t.slot]==-1){ carUsed[t.car]=t.slot; slotUsed[t.slot]=t.car; total+=t.d; }
  for(int i=0;i<C;i++) cout << "Car " << i << " -> Slot " << (carUsed[i]==-1? -1: carUsed[i]) << "\\n";
  cout << "Total (approx): " << total << "\\n";
}

// Bipartite check skeleton
#include <bits/stdc++.h>
using namespace std;
bool is_bipartite(const vector<vector<int>>& g){
  int n=g.size(); vector color(n,-1);
  for(int s=0;s<n;++s){
    if(color[s]!=-1) continue;
    queue q; q.push(s); color[s]=0;
    while(!q.empty()){
      int u=q.front(); q.pop();
      for(int v: g[u]){
        if(color[v]==-1){ color[v]=color[u]^1; q.push(v); }
        else if(color[v]==color[u]) return false;
      }
    }
  }
  return true;
}
int main(){ int n,m; cin>>n>>m; vector<vector>u>>v; g[u].push_back(v); g[v].push_back(u); }
  cout << (is_bipartite(g)? "BIPARTITE":"NOT_BIPARTITE") << "\\n"; return 0;
}

// Greedy Max-Coverage skeleton
#include <bits/stdc++.h>
using namespace std;
struct Fenwick { int n; vector bit; Fenwick(int n=0):n(n),bit(n+1,0){}; void add(int i,long long v){ for(++i;i<=n;i+=i&-i) bit[i]+=v; } long long sum(int i){ long long r=0; for(++i;i>0;i-=i&-i) r+=bit[i]; return r; } };
int main(){
  int P,C,k; cin>>P>>C>>k;
  vector<pair w(P);
  for(int i=0;i<P;i++) cin>>pts[i].first>>pts[i].second>>w[i];
  vector<pair>cand[i].first>>cand[i].second;
  int r; cin>>r;
  vector<vectorbestgain){ bestgain=gain; best=i; }
    }
    if(best==-1) break;
    chosen.push_back(best);
    for(int p:covers[best]) covered[p]=true;
  }
  long long total=0; for(int i=0;i<P;i++) if(covered[i]) total+=w[i];
  cout << "Chosen sites: "; for(int x:chosen) cout << x << " "; cout << "\\nCovered pop: " << total << "\\n";
}

// formula skeleton
#include <bits/stdc++.h>
using namespace std;
double polygon_area(const vector<pair>n; vector<pair>poly[i].first>>poly[i].second; cout << polygon_area(poly) << "\\n"; }

// 2D prefix sums skeleton
#include <bits/stdc++.h>
using namespace std;
int main(){
  int W,H; cin>>W>>H; int T; cin>>T;
  vector<vector(W,0));
  for(int i=0;i<T;i++){ int x,y; cin>>x>>y; if(x>=0&&x<W&&y>=0&&y<H) grid[y][x]++; }
  vector<vector(W+1,0));
  for(int r=1;r<=H;r++) for(int c=1;c<=W;c++) ps[r][c]=grid[r-1][c-1]+ps[r-1][c]+ps[r][c-1]-ps[r-1][c-1];
  int k; cin>>k; vector<pair
              

// Multi-source BFS skeleton
#include <bits/stdc++.h>
using namespace std;
int main(){
  int R,C; cin>>R>>C; vector<string> grid(R);
  for(int i=0;i<R;i++) cin>>grid[i];
  queue<pair(C,-1));
  for(int r=0;r<R;r++) for(int c=0;c<C;c++) if(grid[r][c]=='S'){ dist[r][c]=0; q.push({r,c}); }
  int dr[4]={1,-1,0,0}, dc[4]={0,0,1,-1};
  while(!q.empty()){ auto [r,c]=q.front(); q.pop();
    for(int k=0;k<4;k++){ int nr=r+dr[k], nc=c+dc[k];
      if(nr>=0 && nr<R && nc>=0 && nc<C && grid[nr][nc]!='#' && dist[nr][nc]==-1){ dist[nr][nc]=dist[r][c]+1; q.push({nr,nc}); } }
  }
  for(int r=0;r<R;r++){ for(int c=0;c<C;c++) cout << (dist[r][c]==-1? -1: dist[r][c]) << " "; cout << "\\n"; }
}

// Bridge detection skeleton
#include <bits/stdc++.h>
using namespace std;
void dfs(int u,int p,const vector>& g,vector& tin,vector& low,vector& vis,int &timer,vector>& bridges){
  vis[u]=1; tin[u]=low[u]=++timer;
  for(int v: g[u]){
    if(v==p) continue;
    if(vis[v]) low[u]=min(low[u], tin[v]);
    else{
      dfs(v,u,g,tin,low,vis,timer,bridges);
      low[u]=min(low[u], low[v]);
      if(low[v] > tin[u]) bridges.push_back({u,v});
    }
  }
}
int main(){ int n,m; cin>>n>>m; vector> g(n); for(int i=0;i<m;i++){ int u,v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); }
  vector tin(n,-1), low(n,-1), vis(n,0); int timer=0; vector> bridges;
  for(int i=0;i<n;i++) if(!vis[i]) dfs(i,-1,g,tin,low,vis,timer,bridges);
  for(auto &b:bridges) cout << "Bridge: " << b.first << " - " << b.second << "\\n";
}

// A* / Dijkstra skeleton for grid pathfinding (mark path blocked and next)
#include <bits/stdc++.h>
using namespace std;
using pii = pair;
int heuristic(pii a, pii b){ return abs(a.first-b.first) + abs(a.second-b.second); }
int main(){
  ios::sync_with_stdio(false); cin.tie(nullptr);
  int R,C; cin>>R>>C; vector<string> grid(R);
  for(int i=0;i<R;i++) cin>>grid[i];
  int U; cin>>U; vector<pair<pii,pii>> req(U);
  for(int i=0;i<U;i++){ int sr,sc,gr,gc; cin>>sr>>sc>>gr>>gc; req[i]={{sr,sc},{gr,gc}}; }
  vector<vector(C,0));
  auto inb=[&](int r,int c){ return r>=0 && r<R && c>=0 && c<C; };
  int dr[4]={1,-1,0,0}, dc[4]={0,0,1,-1};
  for(int u=0;u<U;u++){
    auto [s,g] = req[u];
    priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<tuple<int,int,int>>> pq;
    vector<vector(C, INT_MAX)); vector<vector<pii>> parent(R, vector<pii>(C,{-1,-1}));
    dist[s.first][s.second]=0; pq.push({0,s.first,s.second});
    while(!pq.empty()){
      auto [d,r,c]=pq.top(); pq.pop();
      if(d!=dist[r][c]) continue;
      if(r==g.first && c==g.second) break;
      for(int k=0;k<4;k++){ int nr=r+dr[k], nc=c+dc[k]; if(!inb(nr,nc)) continue; if(grid[nr][nc]=='#') continue; if(blocked[nr][nc]) continue;
        if(dist[nr][nc] > d+1){ dist[nr][nc]=d+1; parent[nr][nc]={r,c}; pq.push({dist[nr][nc], nr, nc}); }
      }
    }
    if(dist[g.first][g.second]==INT_MAX){ cout << "Utility " << u << " cannot be routed\\n"; continue; }
    vector<pii> path; pii cur=g; while(!(cur==s)){ path.push_back(cur); cur=parent[cur.first][cur.second]; } path.push_back(s); reverse(path.begin(), path.end());
    for(auto &p:path) blocked[p.first][p.second]=1;
    cout << "Utility " << u << " routed length " << path.size()-1 << "\\n";
  }
  return 0;
}