QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#664375#5426. Drain the Water TankLyniaWA 0ms3840kbC++2315.7kb2024-10-21 20:22:152024-10-21 20:22:15

Judging History

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

  • [2024-10-21 20:22:15]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3840kb
  • [2024-10-21 20:22:15]
  • 提交

answer

///////////        
//                   //      //
//              ////////////////////
//                   //      //
//                 
///////////

//          
//          
//           //     //    ////////     /\     /////////
//           //     //   //      //          //       //
//            ////////   //      //    //    //       //
//                  //   //      //    //    //       //
//////////   ////////    //      //    //     /////////////

#pragma GCC optimize(2)
#pragma G++ optimize(2)
#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
#define DEBUG(a) cout<<a<<endl

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;
}

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"
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>;

namespace Geo {
	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
	}

	// 两点距离
	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) {
		return A.x * B.x + A.y * B.y;
	}

	// 叉积
	template<typename T>
	T cross(const Vector<T>& A, const Vector<T>& B) {
		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 area2(const Point<T>& A, const Point<T>& B, const Point<T>& C) {
		return cross(B - A, C - A);
	}

	// 向量旋转	
	/*
		特殊情况是旋转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_is_on_segment(const Point<T>& p, const Line<T>& v) { // 点和线段:0 点不在线段v上;1 点在线段v上
		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) {
		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) {
		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>
	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>
	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_is_on_segment(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(const vector<Point<T>>& p) {
		Polygon<T> ch;
		int n = p.size();
		n = unique(p.begin(), p.end()) - p;    // 去除重复点    
		ch.resize(n);
		sort(p.begin(), p.begin() + n);        // 对点排序:按 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) // 把后面 ch[v-1] 改成 ch[v-2] 也行
				v--;
			ch[v++] = p[i];
		}
		int j = v;
		// 求上凸包
		for (int i = n - 2; i >= 0; i--) {
			while (v > j && sgn(cross(ch[v - 1] - ch[v - 2], p[i] - ch[v - 1])) <= 0) // 把后面 ch[v-1] 改成 ch[v-2] 也行
				v--;
			ch[v++] = p[i];
		}
		ch.erase(unique(ch.begin(), ch.end()), ch.end());
		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>
class Point {
public:
	T x, y;
	Point(T x = 0, T y = 0) : x(x), y(y) {}

	// 向量长度
	T len() {
		return sqrt(len2());
	}
	// 向量长度的平方
	T len2() {
		return (*this) * (*this);
	}

	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 Geo::sgn(x - B.x) == 0 && Geo::sgn(y - B.y) == 0; }
	bool operator!= (const Point& B) const { return Geo::sgn(x - B.x) || Geo::sgn(y - B.y); }
	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 (Geo::sgn(angle - Geo::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 (Geo::sgn(a) == 0) {
			p1 = Point<T>(0, -c / b);
			p2 = Point<T>(1, -c / b);
		}
		else if (Geo::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 Point<T>& a) { out << a.x << ',' << a.y; return out; }
};

template<typename T>
class Polygon : public vector<Point<T>> {
public:
	Polygon(int n) :vector<Point<T>>(n) {};

	friend ostream& operator<<(ostream& out, const Polygon<T>& a) {
		for (auto& i : a)
			out << i << ' ';
		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; }
	friend ostream& operator<<(ostream& out, const Circle<T>& a) {
		out << a.c << ',' << a.r;
		return out;
	}
};

const int mod = 998244353;
const int N = 1e6 + 10;

void solve(int CASE)
{
	int n; cin >> n;
	var p = Polygon<ll>(n);
	fa(i, 0, n - 1) {
		ll x, y; cin >> x >> y;
		p[i] = { x,y };
	}
	int j = 1;
	int ans = 0;
	fa(i, 0, n - 1) {
		// j 是下一个 y 值与 i 不同的点
		while (p[j].y == p[i].y) j = (j + 1) % n;
		// i 的上一个点
		int pre = (i + n - 1) % n;

		// 如果 i 点在低处,且这个低处之前没有设坑位
		if (p[pre].y > p[i].y and p[j].y > p[i].y) {
			int next = (i + 1) % n; // i 实际上的下一个点


				if (p[next].x >= p[i].x)ans++;
			
		}
	}
	cout << ans << 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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3840kb

input:

6
0 0
1 1
2 1
3 0
3 2
0 2

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

8
4 4
0 4
0 2
1 2
2 2
2 0
3 0
4 0

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

7
1 0
3 4
0 3
1 2
2 3
1 1
0 2

output:

2

result:

ok 1 number(s): "2"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3504kb

input:

6
0 0
2 0
1 1
4 1
5 0
3 4

output:

1

result:

wrong answer 1st numbers differ - expected: '2', found: '1'