GPMB - Giải phóng mặt bằng

Tác giả: ll931110

Ngôn ngữ: C++

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define maxn 1505
using namespace std;

pair<int,int> point[maxn];
int cost[maxn],n;

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d %d %d", &point[i].first, &point[i].second, &cost[i]);
    cost[i] = cost[i] * cost[i] + 5;
  }
  int ret = 0;

  for (int i = 0; i < n; i++) {
    int insideCost = 0;
    vector< pair<double,int> > v;
    for (int j = 0; j < n; j++) if (point[i] == point[j]) insideCost += cost[i]; else {
      double mx = point[j].first - point[i].first,my = point[j].second - point[i].second;
      v.push_back(make_pair(atan2(my,mx),cost[j]));
    }
    sort(v.begin(),v.end());
    int outsideCost = 0,curCost = 0;;
    for (int j = 0; j < v.size(); j++) {
      if (!j || v[j].first > v[j - 1].first) curCost = 0;
      curCost += v[j].second;
      outsideCost = max(outsideCost,curCost);
    }
    ret = max(ret,insideCost + outsideCost);
  }
  
  printf("%d\n", ret);
}

Download