QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#754524 | #7906. Almost Convex | Lynia | AC ✓ | 327ms | 4000kb | C++23 | 21.9kb | 2024-11-16 15:14:36 | 2024-11-16 15:14:36 |
Judging History
answer
///////////
// // //
// ////////////////////
// // //
//
///////////
//
//
// // // //////// /\ /////////
// // // // // // //
// //////// // // // // //
// // // // // // //
////////// //////// // // // /////////////
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <cstring>
#include <cmath>
#include <list>
#include <stack>
#include <array>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <random>
#include <numeric>
#include <functional>
//#include <Windows.h>
using namespace std;
#define fa(i,op,n) for (int i = op; i <= n; i++)
#define fb(j,op,n) for (int j = op; j >= n; j--)
#define pb push_back
#define HashMap unordered_map
#define HashSet unordered_set
#define var auto
#define all(i) i.begin(), i.end()
#define all1(i) i.begin() + 1,i.end()
#define endl '\n'
#define px first
#define py second
using VI = vector<int>;
using VL = vector<long long>;
using ll = long long;
using ull = unsigned long long;
using db = double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<class T1, class T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& p) {
out << '(' << p.first << ", " << p.second << ')';
return out;
}
template<typename T>
ostream& operator<<(ostream& out, const vector<T>& ve) {
for (T i : ve)
out << i << ' ';
return out;
}
template<class T1, class T2>
ostream& operator<<(ostream& out, const map<T1, T2>& mp) {
for (auto i : mp)
out << i << '\n';
return out;
}
template<typename ...T>
bool _debug(T... a) {
((cout << a << ' '), ...);
cout << endl;
return -1;
}
const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
const int IINF = 0x7fffffff;
const int iinf = 0x80000000;
const ll LINF = 0x7FFFFFFFFFFFFFFF;
const ll linf = 0x8000000000000000;
int dx[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };
int dy[8] = { 0, 0, 1, -1, 1, -1, -1, 1 };
//#include "Lynia.h"
namespace MyTools
{
template <typename T>
class Math;
template <const int T>
class ModInt;
namespace Geo {
template<typename T>
class Point;
template<typename T>
class Line;
template<typename T>
class Polygon;
template<typename T>
class Circle;
template<typename T>
using Vector = Point<T>;
template<typename T>
using Segment = Line<T>;
const double eps = 1e-8;
const double PI = acos(-1.0);
// 浮点数 x 的符号
template<typename T>
int sgn(T x) {
if (fabs(x) < eps) return 0;
return x > 0 ? 1 : -1;
}
// 比较两个浮点数
template<typename T>
int cmp(T x, T y) {
if (fabs(x) < eps)return 0; // x == y,返回 0
else return x < y ? -1 : 1; // x < y,返回 -1; x > y,返回 1
}
double radians(double degrees) {
return degrees * PI / 180.0;
}
// 两点距离
template<typename T>
T dist(const Point<T>& A, const Point<T>& B) {
return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
// 点积
template<typename T>
T dot(const Vector<T>& A, const Vector<T>& B) {
// a · b = |a| |b| cos
// 可用于判断两向量夹角
return A.x * B.x + A.y * B.y;
}
// 叉积
template<typename T>
T cross(const Vector<T>& A, const Vector<T>& B) {
// a · b = |a| |b| sin
// 可以判断两向量的相对方向
// 也能算两向量形成的平行四边形面积
return A.x * B.y - A.y * B.x;
}
// 向量长度
template<typename T>
T len(const Vector<T>& A) {
return sqrt(dot(A, A));
}
// 向量长度的平方
template<typename T>
T len2(const Vector<T>& A) {
return dot(A, A);
}
// 两向量夹角
template<typename T>
double angle(const Vector<T>& A, const Vector<T>& B) {
return acos(dot(A, B) / len(A) / len(B));
}
// 计算两向量构成的平行四边形有向面积
// 三个点A、B、C,以A为公共点,得到2个向量B-A和C-A,它们构成的平行四边形
template<typename T>
T area_parallelogram(const Point<T>& A, const Point<T>& B, const Point<T>& C) {
return -cross(B - A, C - A);
}
// 计算两向量构成的平行四边形有向面积
// 两个有公共点的向量 A B 构成的平行四边形
// A B 要按逆时针顺序
template<typename T>
T area_parallelogram(const Vector<T>& A, const Vector<T>& B) {
return cross(A, B);
}
// 计算两向量构成的三角形有向面积
// 三个点A、B、C,以A为公共点,得到2个向量B-A和C-A,它们构成的三角形
template<typename T>
T area_triangle(const Point<T>& A, const Point<T>& B, const Point<T>& C) {
return -cross(B - A, C - A) / 2.0;
}
// 计算两向量构成的三角形有向面积
// 两个有公共点的向量 A B 构成的三角形
// A B 要按逆时针顺序
template<typename T>
T area_triangle(const Vector<T>& A, const Vector<T>& B) {
return cross(A, B) / 2.0;
}
// 向量旋转
/*
特殊情况是旋转90度:
逆时针旋转90度:Rotate(A, pi/2),返回Vector(-A.y, A.x);
顺时针旋转90度:Rotate(A, -pi/2),返回Vector(A.y, - A.x)。
*/
template<typename T>
Vector<T> rotate(const Vector<T>& A, double rad) {
return Vector<T>(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));
}
// 有时需要求单位法向量,即逆时针转90度,然后取单位值。
template<typename T>
Vector<T> normal(const Vector<T>& A) {
return Vector<T>(-A.y / len(A), A.x / len(A));
}
// 两个向量是否平行或重合
template<typename T>
bool parallel(const Vector<T>& A, const Vector<T>& B) {
return sgn(cross(A, B)) == 0; // 返回true表示平行或重合
}
// 点和直线的位置关系
template<typename T>
int point_line_relation(const Point<T>& p, const Line<T>& v) {
int c = sgn(cross(p - v.p1, v.p2 - v.p1));
if (c < 0)return 1; // 1 :p在v的左边
if (c > 0)return 2; // 2 :p在v的右边
return 0; // 0 :p在v上
}
// 点和线段的位置关系
template<typename T>
bool point_segment_relation(const Point<T>& p, const Line<T>& v) {
// 0 点不在线段v上
// 1 点在线段v上
// 前者为 True 说明 p 和 线段 v 的一个端点连边,和 v 本身的夹角为 0,即 p 在 直线 v 上
// 后者为 True 说明 p 和两端点形成平角,也就是说 p 在两端点之间
return sgn(cross(p - v.p1, v.p2 - v.p1)) == 0 && sgn(dot(p - v.p1, p - v.p2)) <= 0;
}
// 点到直线的距离
template<typename T>
double point_line_dis(const Point<T>& p, const Line<T>& v) {
// 实际上是算了 p 和 v 的一个端点连边,然后和 v 形成的平行四边形的面积,除底得到
return fabs(cross(p - v.p1, v.p2 - v.p1)) / dist(v.p1, v.p2);
}
// 点在直线上的投影
template<typename T>
Point<T> point_line_proj(const Point<T>& p, const Line<T>& v) {
double k = dot(v.p2 - v.p1, p - v.p1) / len2(v.p2 - v.p1);
return v.p1 + (v.p2 - v.p1) * k;
}
// 点关于直线的对称点
template<typename T>
Point<T> point_line_symmetry(const Point<T>& p, const Line<T>& v) {
Point<T> q = point_line_proj(p, v);
return Point<T>(2 * q.x - p.x, 2 * q.y - p.y);
}
// 点到线段的距离
template<typename T>
double point_segment_dis(const Point<T>& p, const Segment<T>& v) {
// 先检查点 p 到线段 v 的投影是否在线段 v 上
// 如果在,就直接返回点 p 到直线 v 距离
// 如果不在,就返回线段 v 两端点里 p
// p 先和 v 的两端点比较,看看是否两向量夹角 > 90
if (sgn(dot(p - v.p1, v.p2 - v.p1)) < 0 || sgn(dot(p - v.p2, v.p1 - v.p2)) < 0)
return min(dist(p, v.p1), dist(p, v.p2)); // 点的投影不在线段上
return point_line_dis(p, v); // 点的投影在线段上
}
// 叉积判断两条向量的位置关系,AB * AC,两向量共点
template<typename T>
int vector_vector_relation(const Vector<T>& v1, const Vector<T>& v2) {
int sign = sgn(cross(v1, v2));
if (sign == 0)return 0; // 共线
if (sign > 0)return 1; // v2 在 v1 的逆时针方向
if (sign < 0)return 2; // v2 在 v1 的顺时针方向
}
// 叉积判断两条直线的位置关系
template<typename T>
int line_line_relation(const Line<T>& v1, const Line<T>& v2) {
if (sgn(cross(v1.p2 - v1.p1, v2.p2 - v2.p1)) == 0) {
if (point_line_relation(v1.p1, v2) == 0) return 1; // 1: 重合
else return 0; // 0: 平行
}
return 2; // 2: 相交
}
// 两向量夹角类型
template<typename T>
int vector_vector_angle_type(const Vector<T>& v1, const Vector<T>& v2) {
// 0:夹角度为 0
// 1:夹角为锐角
// 2:夹角为钝角
// 3:夹角为平角,即方向相反
var _dot = dot(v1, v2);
if (vector_vector_relation(v1, v2) == 0) { // 两向量共线
if (sgn(_dot) > 0)return 0;
else return 3;
}
else {
if (sgn(_dot) > 0)return 1;
else return 2;
}
}
// 两条直线的交点
template<typename T>
Point<T> line_line_cross_point(const Point<T>& a, const Point<T>& b, const Point<T>& c, const Point<T>& d) {
// Line1 : ab, Line2 : cd
double s1 = cross(b - a, c - a);
double s2 = cross(b - a, d - a); // 叉积有正负
return Point<T>(c.x * s2 - d.x * s1, c.y * s2 - d.y * s1) / (s2 - s1);
}
// 两条直线的交点
template<typename T>
Point<T> line_line_cross_point(const Line<T>& x, const Line<T>& y) {
// Line1 : ab, Line2 : cd
var a = x.p1;
var b = x.p2;
var c = y.p1;
var d = y.p2;
double s1 = cross(b - a, c - a);
double s2 = cross(b - a, d - a); // 叉积有正负
return Point<T>(c.x * s2 - d.x * s1, c.y * s2 - d.y * s1) / (s2 - s1);
}
// 两个线段是否相交
template<typename T>
bool segment_segment_is_cross(const Point<T>& a, const Point<T>& b, const Point<T>& c, const Point<T>& d) {
// Line1 : ab, Line2 : cd
double c1 = cross(b - a, c - a), c2 = cross(b - a, d - a);
double d1 = cross(d - c, a - c), d2 = cross(d - c, b - c);
return sgn(c1) * sgn(c2) < 0 && sgn(d1) * sgn(d2) < 0; // 1: 相交;0: 不相交
}
// 点和多边形的关系
template<typename T>
int point_polygon_relation(const Point<T>& pt, const Polygon<T>& p) {
// 点pt,多边形 p
int n = p.size();
for (int i = 0; i < n; i++) { // 枚举点
if (p[i] == pt) return 3; // 3:点在多边形的顶点上
}
for (int i = 0; i < n; i++) { // 枚举边
Line<T> v = Line<T>(p[i], p[(i + 1) % n]);
if (point_segment_relation(pt, v)) return 2; // 2:点在多边形的边上
}
// 通过射线法计算点是否在多边形内部 (具体原理可以看书)
int num = 0;
for (int i = 0; i < n; i++) {
int j = (i + 1) % n;
int c = sgn(cross(pt - p[j], p[i] - p[j]));
int u = sgn(p[i].y - pt.y);
int v = sgn(p[j].y - pt.y);
if (c > 0 && u < 0 && v >= 0) num++;
if (c < 0 && u >= 0 && v < 0) num--;
}
return num != 0; // 1:点在内部; 0:点在外部
}
// 计算多边形周长
template<typename T>
T polygon_perimeter(const Polygon<T>& p) {
T ans = 0;
int n = p.size();
for (int i = 0; i < n; i++)
ans += dist(p[i], p[(i + 1) % n]);
return ans;
}
// 多边形的面积
template<typename T>
T polygon_area(const Polygon<T>& p) {
/*
注意面积存在 正负
逆时针遍历点算出来就是正的
顺时针遍历点算出来就是负的
*/
T area = 0;
int n = p.size();
for (int i = 0; i < n; i++)
area += cross(p[i], p[(i + 1) % n]);
return area / 2;
}
// 多边形的重心
template<typename T>
Point<T> polygon_center_point(const Polygon<T>& p) { //求多边形重心
Point<T> ans(0, 0);
int n = p.size();
if (polygon_area(p, n) == 0) return ans;
for (int i = 0; i < n; i++)
ans = ans + (p[i] + p[(i + 1) % n]) * cross(p[i], p[(i + 1) % n]);
return ans / polygon_area(p, n) / 6;
}
/*
求凸包,凸包顶点放在ch中
凸多边形:是指所有内角大小都在 [0, 180] 范围内的简单多边形
凸包:在平面上能包含所有给定点的最小凸多边形叫做凸包
*/
template<typename T>
Polygon<T> convex_hull(vector<Point<T>> p) {
Polygon<T> ch;
if (p.size() == 0 or p.size() == 1 or p.size() == 2) {
for (var& i : p) ch.pb(i);
return ch;
}
// Andrew 法:
// 先对所有点排序
// 求上下凸包 (查每个边相较于上一条边的拐弯方向)
// 然后合并
// 最后得到的点是按照原点的逆时针顺序的
int n = p.size();
n = unique(p.begin(), p.end()) - p.begin(); // 去除重复点
ch.resize(2 * n);
sort(p.begin(), p.end()); // 对点排序:按 x 从小到大排序,如果 x 相同,按 y 排序
int v = 0;
// 求下凸包,如果p[i]是右拐弯的,这个点不在凸包上,往回退
for (int i = 0; i < n; i++) {
while (v > 1 && sgn(cross(ch[v - 1] - ch[v - 2], p[i] - ch[v - 1])) <= 0)
v--;
ch[v++] = p[i];
}
// 求上凸包
for (int i = n - 1, j = v; i >= 0; i--) {
while (v > j && sgn(cross(ch[v - 1] - ch[v - 2], p[i] - ch[v - 1])) <= 0)
v--;
ch[v++] = p[i];
}
ch.resize(v - 1);
return ch;
}
// 点和圆的关系,根据点到圆心的距离判断
template<typename T>
int point_circle_relation(const Point<T>& p, const Circle<T>& C) {
double dst = dist(p, C.c);
if (sgn(dst - C.r) < 0) return 0; // 0: 点在圆内
if (sgn(dst - C.r) == 0) return 1; // 1: 圆上
return 2; // 2: 圆外
}
// 直线和圆的关系,根据圆心到直线的距离判断
template<typename T>
int line_circle_relation(const Line<T>& v, const Circle<T>& C) {
double dst = point_line_dis(C.c, v);
if (sgn(dst - C.r) < 0) return 0; // 0: 直线和圆相交
if (sgn(dst - C.r) == 0) return 1; // 1: 直线和圆相切
return 2; // 2: 直线在圆外
}
// 线段和圆的关系,根据圆心到线段的距离判断
template<typename T>
int segment_circle_relation(const Segment<T> v, const Circle<T> C) {
double dst = point_segment_dis(C.c, v);
if (sgn(dst - C.r) < 0) return 0; // 0: 线段在圆内
if (sgn(dst - C.r) == 0) return 1; // 1: 线段和圆相切
return 2; // 2: 线段在圆外
}
//pa, pb是交点。返回值是交点个数
template<typename T>
int line_cross_circle(const Line<T>& v, const Circle<T>& C, Point<T>& p1, Point<T>& p2) {
if (line_circle_relation(v, C) == 2) return 0; // 无交点
Point<T> q = point_line_proj(C.c, v); // 圆心在直线上的投影点
double d = point_line_dis(C.c, v); // 圆心到直线的距离
double k = sqrt(C.r * C.r - d * d);
if (sgn(k) == 0) { // 1个交点,直线和圆相切
p1 = q; p2 = q; return 1;
}
Point<T> n = (v.p2 - v.p1) / len(v.p2 - v.p1); // 单位向量
p1 = q + n * k; p2 = q - n * k;
return 2; // 2个交点
}
// 弧度制
template<typename T>
double circle_arc_area(const Circle<T>& c, const db& angle) {
return c.area() * angle / 360.0;
}
template<typename T>
double circle_area(const Circle<T>& c) {
return c.area();
}
// 极角排序
template<typename T>
void angle_polar_sort(vector<Point<T>>& points, const Point<T>& reference = Point<T>(0, 0)) {
sort(points.begin(), points.end(),
[&](const Point<T>& a, const Point<T>& b)
{ return a.polar_angle(reference) < b.polar_angle(reference); });
}
template<typename T>
class Point {
private:
int id;
public:
T x, y;
Point(T x = 0, T y = 0) : x(x), y(y), id(0) {}
// this 点相较于 reference 点的极角
double polar_angle(const Point<T>& reference = Point(0, 0)) const {
return atan2(y - reference.y, x - reference.x);
}
T len() const { return sqrt(len2()); } // 向量长度
T len2() const { return (*this) * (*this); } // 向量长度的平方
bool hf() {
return x > 0 || x == 0 && y > 0;
}
void set_id(int id) { this->id = id; }
int get_id()const { return id; }
Point operator- (const Point& B) const { return Point(x - B.x, y - B.y); }
Point operator+ (const Point& B) const { return Point(x + B.x, y + B.y); }
T operator^ (const Point<T>& B) const { return x * B.y - y * B.x; } // 叉积
T operator* (const Point<T>& B) const { return x * B.x + y * B.y; } // 点积
Point operator* (const T& B) const { return Point(x * B, y * B); }
Point operator/ (const T& B) const { return Point(x / B, y / B); }
bool operator< (const Point& B) const { return x < B.x || (x == B.x && y < B.y); }
bool operator> (const Point& B) const { return x > B.x || (x == B.x && y > B.y); }
bool operator== (const Point& B) const { return x == B.x && y == B.y; }
bool operator!= (const Point& B) const { return !(*this == B); }
friend ostream& operator<<(ostream& out, const Point& a) {
out << '(' << a.x << ", " << a.y << ')';
return out;
}
};
template<typename T>
class Line {
public:
Point<T> p1, p2; // 线上的两个点
Line() {}
Line(Point<T> p1, Point<T> p2) :p1(p1), p2(p2) {}
Line(Point<T> p, double angle) { // 根据一个点和倾斜角 angle 确定直线,0 <= angle < pi
p1 = p;
if (sgn(angle - PI / 2) == 0) { p2 = (p1 + Point<T>(0, 1)); }
else { p2 = (p1 + Point<T>(1, tan(angle))); }
}
Line(double a, double b, double c) { // ax + by + c = 0
if (sgn(a) == 0) {
p1 = Point<T>(0, -c / b);
p2 = Point<T>(1, -c / b);
}
else if (sgn(b) == 0) {
p1 = Point<T>(-c / a, 0);
p2 = Point<T>(-c / a, 1);
}
else {
p1 = Point<T>(0, -c / b);
p2 = Point<T>(1, (-c - a) / b);
}
}
friend ostream& operator<<(ostream& out, const Line<T>& a) {
out << "[" << a.p1 << ", " << a.p2 << "]";
return out;
}
// 计算斜率 k
double k() const {
if (sgn(p2.x - p1.x) == 0) { // 垂直线,斜率不存在
throw runtime_error("Vertical line has undefined slope.");
}
return double(p2.y - p1.y) / (p2.x - p1.x);
}
// 计算截距 b
double b() const {
if (sgn(p2.x - p1.x) == 0) { // 垂直线,斜率不存在
throw runtime_error("Vertical line does not have a y-intercept.");
}
double _k = k();
return p1.y - _k * p1.x;
}
};
template<typename T>
class Polygon : public vector<Point<T>> {
public:
Polygon() {}
Polygon(int n) :vector<Point<T>>(n) {}
// 多边形的周长
T Perimeter() {
T ans = 0;
int n = this->size();
for (int i = 0; i < n; i++)
ans += dist((*this)[i], (*this)[(i + 1) % n]);
return ans / 2.0;
}
// 多边形的面积
T Area() {
T area = 0;
int n = this->size();
for (int i = 0; i < n; i++)
area += cross((*this)[i], (*this)[(i + 1) % n]);
return area;
}
// 极角排序,默认逆时针排序
void Polar_angle_sort(const Point<T>& reference = Point<T>(0, 0)) {
sort(this->begin(), this->end(),
[&](const Point<T>& a, const Point<T>& b)
{ return a.polar_angle(reference) < b.polar_angle(reference); });
}
friend ostream& operator<<(ostream& out, const Polygon<T>& a) {
out << "[";
for (int i = 0; i < a.size(); i++)
out << a[i] << ",]"[i == a.size() - 1];
return out;
}
};
template<typename T>
class Circle {
public:
Point<T> c; // 圆心
T r; // 半径
Circle() {}
Circle(Point<T> c, T r) :c(c), r(r) {}
Circle(T x, T y, T _r) { c = Point<T>(x, y); r = _r; }
double area() const { return PI * r * r; }
// 弧度制
double arc_area(const db& angle) const { return area() * angle / 360.0; }
friend ostream& operator<<(ostream& out, const Circle<T>& a) {
out << "(" << a.c << ", " << a.r << ")";
return out;
}
};
}
}
namespace MT = MyTools;
using Math = MT::Math<ll>;
#define geo MT::Geo
const int mod = 1e9 + 7;
using mint = MT::ModInt<mod>;
const int N = 1e6 + 10;
void solve(int CASE)
{
int n; cin >> n;
var p = geo::Polygon<db>();
fa(i, 1, n) {
int x, y; cin >> x >> y;
var point = geo::Point<db>(x, y);
point.set_id(i);
p.pb(point);
}
var vis = vector<bool>(n + 1);
var&& hull = geo::convex_hull(p);
for (var& i : hull)vis[i.get_id()] = 1;
var pp = geo::Polygon<db>();
for (var& i : p)if (!vis[i.get_id()])pp.pb(i);
int ans = 0;
for (var& point : pp) {
// 剩下的以 point 为参考点极角排序
var rest = geo::Polygon<db>();
for (var& j : p)if (j != point)rest.pb(j);
sort(all(rest), [&](geo::Point<db> a, geo::Point<db> b)->bool {
a = a - point; b = b - point;
if (a.hf() != b.hf())return a.hf() < b.hf();
return geo::cross(a, b) > 0;
});
int n = rest.size();
for (int i = 1; i < n; i++)
if (vis[rest[i].get_id()] and vis[rest[i - 1].get_id()])
ans++;
// 是个环
if (vis[rest[0].get_id()] and vis[rest[n - 1].get_id()])
ans++;
}
cout << ans + 1 << endl;
return;
}
int main()
{
//SetConsoleOutputCP(CP_UTF8);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int _ = 1;
//cin >> _;
fa(i, 1, _)solve(i);
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3564kb
input:
7 1 4 4 0 2 3 3 1 3 5 0 0 2 4
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
5 4 0 0 0 2 1 3 3 3 1
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
6 0 0 3 0 3 2 0 2 1 1 2 1
output:
7
result:
ok 1 number(s): "7"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
4 0 0 0 3 3 0 3 3
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 314ms
memory: 3760kb
input:
2000 86166 617851 383354 -277127 844986 386868 -577988 453392 -341125 -386775 -543914 -210860 -429613 606701 -343534 893727 841399 339305 446761 -327040 -218558 -907983 787284 361823 950395 287044 -351577 -843823 -198755 138512 -306560 -483261 -487474 -857400 885637 -240518 -297576 603522 -748283 33...
output:
718
result:
ok 1 number(s): "718"
Test #7:
score: 0
Accepted
time: 321ms
memory: 3652kb
input:
2000 571314 -128802 -57762 485216 -713276 485201 -385009 -844644 371507 403789 338703 -272265 -913641 438001 -792118 -481524 709494 213762 -913577 432978 -397111 709021 840950 328210 -843628 452653 -20721 126607 -107804 -338102 930109 -89787 -949115 -76479 -862141 455623 991761 94852 -635475 625573 ...
output:
658
result:
ok 1 number(s): "658"
Test #8:
score: 0
Accepted
time: 317ms
memory: 3760kb
input:
2000 -510540 -289561 -602648 -189950 -403224 944455 -369582 -41334 358122 -598933 -817147 470207 -440180 -735160 -705634 61719 319062 897001 -905089 -755682 -408371 -520115 -423336 548115 -590242 835990 208155 883477 -202087 142035 -71545 411206 570690 -673204 -228451 -903435 -732876 -570271 -246755...
output:
309
result:
ok 1 number(s): "309"
Test #9:
score: 0
Accepted
time: 322ms
memory: 3716kb
input:
2000 -532115 566389 138405 49337 398814 -97324 116833 113216 381728 877609 222402 641022 109920 952381 -113880 395181 13780 -572931 -676608 605202 -74328 -503839 -207767 926500 -663270 -146303 197877 280349 275865 -663892 -630214 3286 973786 304855 -493735 841584 394901 -505975 757960 204724 -373328...
output:
239
result:
ok 1 number(s): "239"
Test #10:
score: 0
Accepted
time: 313ms
memory: 3968kb
input:
2000 512636 509804 -661126 -592269 755566 -721837 -878213 441853 -236050 -89069 -181220 155656 203391 691764 940154 260513 747075 373881 620423 840991 -409624 335472 270937 -710659 -751290 -673585 250341 -193243 -250535 618887 -739996 543936 -547741 -213681 -82920 -364319 -611672 737719 930798 46731...
output:
1025
result:
ok 1 number(s): "1025"
Test #11:
score: 0
Accepted
time: 325ms
memory: 3752kb
input:
2000 943353 817289 237151 899722 682851 -464873 854225 205354 834550 257948 -260874 298196 -224572 -269157 -667301 881130 -45920 -696359 -634337 792620 -408527 -947513 582880 172669 921645 839423 833813 721080 -836662 -287230 -55783 -408594 108996 -122012 365647 -789544 313812 833502 970009 -737736 ...
output:
218
result:
ok 1 number(s): "218"
Test #12:
score: 0
Accepted
time: 320ms
memory: 4000kb
input:
2000 619248 227987 -252490 -553032 148050 -479727 -333707 -591482 -40488 -503144 561909 255624 -402541 -798967 -245811 -610006 -146584 -517935 226433 -92580 -81939 -828480 72540 -845547 502613 220323 66708 -573015 601886 258752 406443 257854 232970 -671600 -37023 -683767 602339 456757 -440096 -71899...
output:
7
result:
ok 1 number(s): "7"
Test #13:
score: 0
Accepted
time: 327ms
memory: 3732kb
input:
2000 -602451 2956 85982 141739 -185932 -208897 -716095 58215 -468047 155612 -791626 -3105 75700 -484098 609608 -304849 689485 -106857 533177 -285261 -659400 -241162 -369302 165482 406663 265940 -353843 -788313 805885 -75440 -571955 -60471 351360 -81373 -510926 -59456 591713 179588 534794 -118 201630...
output:
66
result:
ok 1 number(s): "66"
Test #14:
score: 0
Accepted
time: 315ms
memory: 3936kb
input:
2000 41203 -675424 -158994 366628 -133859 -595680 435466 687630 687811 -35017 314337 133049 -384711 444777 54850 -760922 526166 282618 572292 94793 -324003 621393 -30308 242225 612969 -231837 -56628 -892609 -492077 58749 29597 -349591 198510 219502 380955 -59845 839171 -40068 88185 -820614 -572977 -...
output:
43
result:
ok 1 number(s): "43"
Test #15:
score: 0
Accepted
time: 313ms
memory: 3996kb
input:
2000 -814040 46114 -324077 -522697 388552 -604274 -252898 43028 -757069 141507 413462 -649779 -281915 -316285 -498931 -573214 -408766 670792 -271435 -393170 87187 731739 89312 -853584 -768680 -307261 -185324 234729 -70493 -354866 16452 164338 -650791 -518077 851196 -259322 -85395 -509349 241593 5074...
output:
129
result:
ok 1 number(s): "129"
Test #16:
score: 0
Accepted
time: 316ms
memory: 3708kb
input:
2000 23103 -796677 -148322 67634 -525131 -446626 2672 584671 -712789 -69579 -91150 -429393 -375635 -487235 -680553 -370975 793181 -383683 -234131 -462420 -734705 -171834 322671 -355011 760005 224249 700248 -352775 416862 -125857 -497951 717254 677084 -451876 -220123 616240 525973 -144881 -300828 553...
output:
1466
result:
ok 1 number(s): "1466"
Test #17:
score: 0
Accepted
time: 304ms
memory: 3712kb
input:
2000 -185174 470373 -772343 -70370 -182314 851727 661615 -250979 -581175 527646 332025 141502 -659052 -506788 -378459 -553180 11233 162287 469975 -572356 679074 217029 -137967 727723 581696 140544 452574 -319370 120895 129820 772655 -330960 122860 823902 -786221 147543 -206152 -373647 -212943 4820 6...
output:
2801
result:
ok 1 number(s): "2801"
Test #18:
score: 0
Accepted
time: 298ms
memory: 3764kb
input:
2000 -718158 695879 655921 595312 -509080 -860718 540612 244159 -83221 -865654 -460513 -542465 102321 -775593 328552 799263 -284269 -725108 152140 549502 -108610 465054 -97837 -449762 -772869 -171472 293831 -711723 508617 -157976 170737 323070 544222 385453 -633043 -233165 -620164 -459706 507218 338...
output:
14445
result:
ok 1 number(s): "14445"
Test #19:
score: 0
Accepted
time: 299ms
memory: 3704kb
input:
2000 -587991 -165467 -530325 -5525 -574943 180654 -496535 -748102 -436469 -160646 110285 237070 -822862 -141480 -177189 327799 -424868 331309 -999274 38095 -745710 192605 -234174 -804258 586432 -176239 -626756 499109 -562606 826724 890245 455480 -32262 -298900 550800 516690 -588632 -368654 405331 -3...
output:
64358
result:
ok 1 number(s): "64358"
Test #20:
score: 0
Accepted
time: 241ms
memory: 3716kb
input:
2000 441575 -414673 651578 -449237 287355 -489950 606811 -30288 -733692 679481 -652568 89883 -360110 616801 190405 -368787 -352383 935855 118240 73038 -374899 -927065 -22183 -491455 -146229 638417 998825 -48442 -374469 243261 988830 149043 -778607 -291542 -277026 -167975 372912 -405043 535321 425727...
output:
233885
result:
ok 1 number(s): "233885"
Test #21:
score: 0
Accepted
time: 205ms
memory: 3712kb
input:
2000 -369265 -366669 -225059 -65255 750236 -107534 -252341 967638 533029 -79205 -482639 504243 -164616 -477455 -219649 975578 222020 297565 -548636 -836060 595498 -345235 -971961 -235140 179392 983777 747498 664263 -458850 -513884 -456639 186799 508542 -359953 630300 5257 -294961 -599723 999627 2729...
output:
430546
result:
ok 1 number(s): "430546"
Test #22:
score: 0
Accepted
time: 188ms
memory: 3996kb
input:
2000 -586906 -809654 -279647 960102 -279925 501031 -76716 526333 -277891 -599253 171606 -289251 565124 -825005 -125381 -163097 -71257 -202933 999551 29949 286017 -698748 257733 358898 6047 18648 283230 -959051 221238 -975219 686818 32684 368089 -929790 -689242 449329 -547431 836850 612952 -790120 -9...
output:
484966
result:
ok 1 number(s): "484966"
Test #23:
score: 0
Accepted
time: 178ms
memory: 3652kb
input:
2000 -360385 -932803 6402 -568575 477942 -878390 361387 -497256 -383874 -126116 -838786 214745 157834 -987465 955879 293759 -91170 -521309 262250 964999 883045 -469287 350745 823160 999731 -23179 -791215 8792 208002 153508 -553609 549966 -345358 591962 -613852 198594 81698 996657 803702 98789 201163...
output:
513300
result:
ok 1 number(s): "513300"
Test #24:
score: 0
Accepted
time: 176ms
memory: 3704kb
input:
2000 -996201 87077 834777 -550587 -316381 948632 750921 -473436 -170208 -985408 -98642 17818 735787 -677212 80294 -996771 -420703 594219 995302 -96813 997685 68003 -680287 396657 -986559 163401 313494 442433 -774277 632845 809816 -586683 -569560 692991 956486 -291775 992620 -121264 998004 -63141 -64...
output:
528222
result:
ok 1 number(s): "528222"
Test #25:
score: 0
Accepted
time: 168ms
memory: 3964kb
input:
2000 -876642 481141 513009 -76454 48555 998820 -665181 11267 -681766 -551841 -724328 30683 -594565 -308913 799027 -601295 390878 658489 300660 953731 -227699 973731 621281 283696 871533 490336 -363638 931539 592572 805516 330089 201429 -282723 -959201 -351348 316419 -5935 -999982 -413615 -910451 -14...
output:
527976
result:
ok 1 number(s): "527976"
Test #26:
score: 0
Accepted
time: 165ms
memory: 3700kb
input:
2000 -496177 868221 -142749 -989758 -999462 -32767 -496370 452632 -50957 -998700 549450 25036 -389116 607514 164685 -287576 546553 837424 -356561 934271 250395 -662914 752586 452605 -803752 594963 -978350 206954 983866 178904 -712386 -247430 494205 -869345 777893 628396 -91446 995809 -373660 927565 ...
output:
536419
result:
ok 1 number(s): "536419"
Test #27:
score: 0
Accepted
time: 166ms
memory: 3968kb
input:
2000 -20062 470240 889867 456219 84686 996407 -54908 580599 428693 -903450 -150993 -781447 -437742 -134074 -245186 -299633 216878 730546 -588614 808414 -945245 326360 -72396 -11572 -663429 748238 -538386 842697 463983 400770 716299 697792 161751 -986831 931604 -363474 -466293 884630 163252 -116392 4...
output:
541774
result:
ok 1 number(s): "541774"
Test #28:
score: 0
Accepted
time: 169ms
memory: 3800kb
input:
2000 125380 -992108 876963 480556 -954331 -298750 -872744 488177 -667627 744495 527592 -849497 -41014 -455304 13780 890561 -637070 -474060 858293 513158 -422631 -408446 792248 610198 272933 -962032 768663 -639653 957724 -287686 -655707 -72182 774032 633145 44910 -998991 767034 -220288 32566 -999469 ...
output:
554369
result:
ok 1 number(s): "554369"
Test #29:
score: 0
Accepted
time: 164ms
memory: 3708kb
input:
2000 877194 480134 721871 -692027 -657316 -753614 -141802 690188 -984203 -177038 499512 866306 60213 331650 667197 -744880 790745 -612145 526658 70820 -975342 -220697 -818975 126696 -206901 13958 -217847 783500 -498782 460388 214283 -976771 124783 992183 -826617 562763 -869768 -493460 -360542 721516...
output:
556266
result:
ok 1 number(s): "556266"
Test #30:
score: 0
Accepted
time: 145ms
memory: 4000kb
input:
2000 -928276 -371891 693025 -720912 340453 -741801 -315399 948959 -999987 -5058 957766 -287546 -11785 -999930 -480620 876928 -591790 -806091 430900 -490816 232828 972517 709950 -704252 -784773 619782 -40706 -999171 972505 232879 57240 360935 837945 25369 -349605 -537128 -50451 -998726 357173 300683 ...
output:
578226
result:
ok 1 number(s): "578226"
Test #31:
score: 0
Accepted
time: 131ms
memory: 3740kb
input:
2000 588463 808523 -653251 -757141 -216959 -976180 620816 -783955 -917704 397264 642866 765978 -965972 -258645 -662131 -749387 919793 -392403 81500 -385642 -860281 -509819 -976258 216610 -881856 -471517 781371 -274463 -769776 638313 996471 -83936 -149837 -988710 88728 -996055 621852 -125590 193779 4...
output:
599788
result:
ok 1 number(s): "599788"
Test #32:
score: 0
Accepted
time: 136ms
memory: 3964kb
input:
2000 -713963 -700183 149576 -48137 -904609 -426240 603724 -34474 -350076 178901 -692350 211723 -777299 -629130 -996510 -83463 343004 -939333 696533 554432 -288734 -640484 798029 602618 -327795 -944748 523003 852330 -49570 998770 263409 254892 -314451 619311 -368911 444305 -289455 -406382 -63806 -648...
output:
607941
result:
ok 1 number(s): "607941"
Test #33:
score: 0
Accepted
time: 134ms
memory: 3704kb
input:
2000 -979883 199570 812775 582577 -257939 966161 -874515 -484998 293436 -242001 749548 -288423 -671752 740775 -12769 999918 295251 955419 175054 -13528 -334691 -942327 539352 -842079 705797 -49973 348168 771901 859906 510451 121051 -572684 909626 -415426 -255421 -545286 962040 272906 -813562 581477 ...
output:
605021
result:
ok 1 number(s): "605021"
Test #34:
score: 0
Accepted
time: 131ms
memory: 3696kb
input:
2000 748836 662754 853522 521056 501246 608578 -266167 963926 347098 937828 996632 -82002 300258 -953857 570683 -821169 -399685 -531914 -52991 -536271 -268825 -738298 -440252 449420 936398 350939 -183686 982984 -792809 -609469 -36070 -98167 -769325 638857 957390 288796 -272995 -796868 434336 -294938...
output:
609148
result:
ok 1 number(s): "609148"
Test #35:
score: 0
Accepted
time: 122ms
memory: 3712kb
input:
2000 -75848 997119 -878795 -477199 718319 -695713 -750620 -660733 791233 -261340 734828 678253 -298982 223462 -243124 618205 333026 -942917 -431834 -311408 102455 -779863 839939 542679 -888198 459459 -6972 999975 -989074 147415 619268 -785179 913472 -406900 857133 515094 -490437 715504 187406 842078...
output:
612907
result:
ok 1 number(s): "612907"
Test #36:
score: 0
Accepted
time: 120ms
memory: 3712kb
input:
2000 710449 252021 -605745 -795658 965777 259370 528796 -506543 7488 -999971 130196 134654 205176 -978725 360847 -549034 940307 340325 -878187 -478317 195786 -980646 -965779 -259362 -40526 404237 926277 -376843 659148 752012 799019 -601305 609935 184334 400162 64645 123163 -992386 440739 80681 61275...
output:
613033
result:
ok 1 number(s): "613033"
Test #37:
score: 0
Accepted
time: 117ms
memory: 3716kb
input:
2000 -280012 -148903 382702 395900 551170 834392 138094 -142893 747764 -321810 814783 -579764 855100 -518462 518036 855358 -308932 768160 -746881 -664957 -550707 -834698 -203567 979060 -94882 211708 954151 299324 995262 -97226 995211 97743 -361441 932394 -879179 -476490 492429 -870352 222424 -974949...
output:
613525
result:
ok 1 number(s): "613525"
Test #38:
score: 0
Accepted
time: 119ms
memory: 3652kb
input:
2000 -31467 999504 -691705 722179 330770 -943711 -868142 496314 534209 -845352 -948997 315285 708054 706157 50035 -880465 -926659 375902 883484 -468460 -569126 -321856 -203339 709769 -569574 -821939 -753190 -657801 997229 -74388 -559117 829088 797882 -602812 -145490 822289 -951880 306469 648629 -418...
output:
609202
result:
ok 1 number(s): "609202"
Test #39:
score: 0
Accepted
time: 117ms
memory: 3964kb
input:
2000 -33027 -231537 645986 -17185 894873 -446319 369601 -929190 -858847 512231 759587 -650405 821506 -570199 64855 -997894 770842 637025 532744 -331176 148586 -77740 -903364 -428872 -999964 -8474 -967232 253890 4771 -999988 -238462 -243104 -936126 351663 987061 160340 508004 131675 -413865 910337 18...
output:
610683
result:
ok 1 number(s): "610683"
Test #40:
score: 0
Accepted
time: 111ms
memory: 3708kb
input:
2000 315983 611022 -710308 -71198 -574424 -609685 286803 957989 -365263 930904 605616 -39979 261643 965164 -34821 -681407 971328 237742 -428673 903459 -348540 -413287 -716611 446376 -389197 -921154 -214771 -976664 469821 -882761 -288792 -516000 451431 892305 665222 46114 -712000 702178 -11820 237318...
output:
606866
result:
ok 1 number(s): "606866"
Test #41:
score: 0
Accepted
time: 107ms
memory: 3652kb
input:
2000 827570 -561361 106486 -994314 531932 -846786 85020 -821614 -861275 508137 -944596 328233 -654160 -756355 -599581 330073 -953317 -301970 -337499 541540 867483 497465 674219 -738530 742712 438360 -431377 463380 -976458 -215705 -920911 389771 -603054 797699 -651789 758400 993338 115232 -653951 756...
output:
605654
result:
ok 1 number(s): "605654"
Test #42:
score: 0
Accepted
time: 105ms
memory: 3716kb
input:
2000 660227 -171320 -66161 -85351 683277 -730158 980572 196158 395353 118603 97015 448847 428573 -903506 927991 372602 615713 -506850 -694999 719010 411175 911556 463884 885895 159594 -724246 8242 747837 605323 -795979 878479 -50570 -395291 918555 476675 -879079 593695 804689 -941633 336639 -875114 ...
output:
607199
result:
ok 1 number(s): "607199"
Test #43:
score: 0
Accepted
time: 105ms
memory: 3708kb
input:
2000 -404720 641654 376493 -278480 678653 734458 767939 -640522 -419247 -907872 -664244 69783 627003 -779016 -990939 -134306 346792 544624 136558 -725588 -595202 803575 -234031 -301953 -299941 -953957 -866081 499902 901591 -432588 200283 979738 -699910 714230 812341 -583182 357149 -381610 -957517 28...
output:
603919
result:
ok 1 number(s): "603919"
Test #44:
score: 0
Accepted
time: 98ms
memory: 3764kb
input:
2000 -599904 800071 -887152 -461476 703155 -711035 653695 756757 -230256 -973129 987562 157229 -610508 173456 -405774 110423 859552 -511046 -901289 433216 913048 407850 640724 -767771 999070 43110 209538 -620478 888118 459614 839191 543836 -676657 469821 525241 850953 -563829 -825890 -688034 -725678...
output:
598805
result:
ok 1 number(s): "598805"
Test #45:
score: 0
Accepted
time: 93ms
memory: 3704kb
input:
2000 956636 291284 -998398 -56572 -877970 -478715 -907198 -420702 512527 858670 -435307 900281 -445471 895295 247912 364785 -348233 -937407 -901447 -432888 -571179 820825 392021 -919956 574003 115097 -265057 -355995 912755 408506 -375400 926862 -993241 116070 695920 -718118 -284145 -958781 -472992 8...
output:
598251
result:
ok 1 number(s): "598251"
Test #46:
score: 0
Accepted
time: 94ms
memory: 3708kb
input:
2000 -764451 644681 531916 -198765 281641 -959519 -815218 -579153 -974347 225046 -949358 314195 28285 744344 69688 -997568 -775844 630924 973439 228945 621650 783294 -628873 -777507 29532 390971 778370 -93337 923334 -383997 -648844 -760921 -37277 -471652 975210 221278 535838 -634598 -843132 537705 1...
output:
588592
result:
ok 1 number(s): "588592"
Test #47:
score: 0
Accepted
time: 90ms
memory: 3656kb
input:
2000 113634 993522 296600 -955001 -983491 180954 969414 -245430 346546 -938032 -222652 -54964 -61422 998111 -183247 -983066 -700935 713224 -729527 683951 785401 -618986 734347 267059 -898291 439399 394552 918873 -999754 -22148 -999082 -42823 -261334 -965248 858996 -511981 388846 528044 398694 917083...
output:
580267
result:
ok 1 number(s): "580267"
Test #48:
score: 0
Accepted
time: 82ms
memory: 3740kb
input:
2000 -999844 17617 825619 -564226 -998793 49111 -342117 -939657 -964696 263365 348225 -937410 -534589 845111 972446 -233128 996396 84812 226108 974102 819673 -572831 787248 -616635 584981 -811046 -91377 -845586 399 -999999 -420017 -907516 -990854 134931 -8366 -653975 -971086 -238729 -910547 413403 7...
output:
574822
result:
ok 1 number(s): "574822"
Test #49:
score: 0
Accepted
time: 89ms
memory: 3700kb
input:
2000 -642241 766502 985145 -171722 960869 -277002 -770518 637417 -997009 -77276 389040 -921220 -625503 -780221 785285 619134 -869488 -493952 399502 -269138 605487 795854 -979953 -199227 -141150 -989988 -59731 -998214 -372142 -928175 430982 -902360 377383 926057 -253882 781247 -610587 -791948 -15523 ...
output:
569661
result:
ok 1 number(s): "569661"
Test #50:
score: 0
Accepted
time: 33ms
memory: 3704kb
input:
2000 -628838 -357590 978524 206130 -759844 650104 325497 945542 743026 669261 -626067 779768 809046 587744 785675 -618639 999954 9576 -917782 397082 594121 804375 479925 174875 362584 -392818 471020 -882122 -958352 -285587 203295 -979117 -101902 -994794 -307252 -951628 -522875 -852408 -999478 -32304...
output:
324930
result:
ok 1 number(s): "324930"
Test #51:
score: 0
Accepted
time: 18ms
memory: 3700kb
input:
2000 973483 228755 -923152 -384434 -974475 224492 -951197 308583 -301050 -953608 623065 782169 -4460 -999990 -347338 937739 -999141 41423 328894 -944366 -695142 -718871 840009 -542572 -226507 974009 472259 -881459 903505 428576 -559822 -828612 642699 766118 548513 -836141 764272 644893 178154 984002...
output:
180726
result:
ok 1 number(s): "180726"
Test #52:
score: 0
Accepted
time: 9ms
memory: 3964kb
input:
2000 -784353 -620314 995900 90455 -116566 -993182 881042 473036 177991 -984032 -999969 7783 655203 755452 -779179 626800 -181243 -983438 274776 -961507 609151 -793054 -1362 -843519 -566798 -823856 -530993 -847375 -951795 306733 62564 -998040 -959361 282180 -964809 -262948 185709 982604 -913941 40584...
output:
95123
result:
ok 1 number(s): "95123"
Test #53:
score: 0
Accepted
time: 2ms
memory: 3708kb
input:
2000 -378825 -925468 260691 -965422 854263 519839 -132682 -991158 -992506 122194 159239 987240 -986433 164163 -821638 -570008 936600 350399 -542405 840116 -116212 -993224 214672 976686 493136 -869952 -970476 241194 -744228 667925 -942833 333263 -884817 -465937 -941813 336134 714086 -700057 -931887 -...
output:
39222
result:
ok 1 number(s): "39222"
Test #54:
score: 0
Accepted
time: 2ms
memory: 3712kb
input:
2000 -982363 -186982 -654678 -755907 -468244 -883598 -999061 43307 -487654 873036 -996826 79600 -712944 -701220 -878254 -478193 -803280 595601 832745 -553656 -997294 73507 -969828 243790 449635 -893212 -180210 983627 582389 -812909 509250 860618 -845162 534508 -949329 314282 -976802 -214139 -414704 ...
output:
19811
result:
ok 1 number(s): "19811"
Test #55:
score: 0
Accepted
time: 1ms
memory: 3736kb
input:
2000 -944717 -327884 24164 -999707 988832 149033 545249 838273 54412 998518 996706 -81087 -632826 774293 971372 237560 -588936 -808179 -721351 -692569 909375 -415975 947390 320078 490265 -871573 770999 -636835 -877832 478968 -364048 -931380 995651 -93159 177569 -984108 945090 -326808 -107026 -994256...
output:
1
result:
ok 1 number(s): "1"
Extra Test:
score: 0
Extra Test Passed