QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#268135#5111. Take On MemejuampiWA 1ms3632kbC++172.3kb2023-11-28 09:29:242023-11-28 09:29:24

Judging History

你现在查看的是最新测评结果

  • [2023-11-28 09:29:24]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3632kb
  • [2023-11-28 09:29:24]
  • 提交

answer

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <functional>
#include <iostream>
#include <tuple>
#include <vector>
using namespace std;


void Init() {
  srand(time(0));
  ios::sync_with_stdio(false);
  cin.tie(NULL);
}

int64_t cmpx = 1, cmpy = 0;
struct Point {
  int64_t x, y;
  Point operator-() const { return {-x, -y}; }
  Point& operator+=(const Point& p) { x += p.x; y += p.y; return *this; }
  Point operator-(const Point& p) const { return {x-p.x, y-p.y}; }
  Point operator+(const Point& p) const { return {x+p.x, y+p.y}; }
  bool operator<(const Point& p) const { return x*cmpx + y*cmpy < p.x*cmpx + p.y*cmpy; }
  bool operator==(const Point& p) const { return x == p.x && y == p.y; }
  Point ortho() const { return {-y, x}; }
  int64_t lensqr() const { return x*x+y*y; }
  void print(){
    cout<<x<<","<<y<<endl;
  }
};

int64_t ret = 0;  // Move ret outside main
vector<vector<int>> ch;
vector<Point> p;

pair<Point,Point> doit(int x){
  if (ch[x].size() == 0) return {p[x], p[x]};
  auto [mntot, mxtot] = doit(ch[x][0]);
  Point mndiff = mxtot+mntot, mxdiff = mndiff;
  for (int i = 1; i < ch[x].size(); i++) {
    auto [mn, mx] = doit(ch[x][i]);
    mntot += mn;
    mxtot += mx;
    mndiff = min(mndiff, mx+mn);
    mxdiff = max(mxdiff, mx+mn);
  }
  return {-mxtot+mndiff, -mntot+mxdiff};
};

tuple<Point, Point> tryAngle(Point dir){
  cmpx = dir.x; cmpy = dir.y;
  auto [mn, mx] = doit(1);
  ret = max(ret, mx.lensqr());
  ret = max(ret, mn.lensqr());
  return {mn, mx};
};

void traceHull(Point a, Point b) {
  a.print();
  b.print();
  if (a == b) return;
  auto [_, c] = tryAngle((b-a).ortho());
  if (a < c) { traceHull(a, c); traceHull(c, b); }
};

int main() {
  Init();

  int N, M;
  while (cin >> N) {
    ch.resize(N + 1);  // Resize ch and p instead of redeclaring
    p.resize(N + 1);
    for (int i = 1; i <= N; i++) {
      cin >> M;
      if (M == 0) {
        cin >> p[i].x >> p[i].y;
      } else {
        ch[i].resize(M);
        for (auto& x : ch[i]) cin >> x;
      }
    }
    ret = 0;

    auto [left, right] = tryAngle({1, 0});
    traceHull(left, right);
    traceHull(right, left);

    printf("%lld\n", ret);
  }
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3632kb

input:

5
4 2 3 4 5
0 2 -2
0 1 3
0 4 -6
0 -18 5

output:

-25,10
19,-12
-25,10
13,6
13,6
19,-12
19,-12
-25,10
725

result:

wrong answer 1st lines differ - expected: '725', found: '-25,10'