QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#268135 | #5111. Take On Meme | juampi | WA | 1ms | 3632kb | C++17 | 2.3kb | 2023-11-28 09:29:24 | 2023-11-28 09:29:24 |
Judging History
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);
}
}
Details
Tip: Click on the bar to expand more detailed information
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'