挑战程序竞赛2下

	#include <iostream>
	#include <cstdio>
	#include <vector>
	using namespace std;

	class DisjointSet {
	public :
	//rank 记录树的高度
	vector<int> rank, p;
	DisjointSet() {};
	DisjointSet(int size) {
	rank.resize(size, 0);
	p.resize(size, 0);
	for (int i = 0; i < size; i++)
	makeSet(i);
	}
	void makeSet(int i) {
	p[i] = i;
	rank[i] = 0;
	}

	bool same(int x, int y) {
	return findSet(x) == findSet(y);
	}

	void unite(int x, int y) {
	link(findSet(x), findSet(y));
	}

	void link(int x, int y) {
	// 包含 x 的树的高度更高，则将 y 的树合并到 x 上
	if (rank[x] > rank[y])
	p[y] = x;
	else {
	p[x] = y;
	if (rank[x] == rank[y])
	rank[y]++;
	}
	}
	int findSet(int x) {
	if (x != p[x])
	p[x] = findSet(p[x]);
	return p[x];
	}
	};
	int main()
	{
	int n, a, b,t, q;
	scanf("%d %d", &n, &q);
	DisjointSet ds = DisjointSet(n);
	for (int i = 0; i < q; i++) {
	scanf("%d %d %d", &t, &a, &b);
	if (t == 0)
	ds.unite(a, b);
	else
	printf("%d\n", ds.same(a, b) ? 1 : 0);
	}
	return 0;
	}

	#include <iostream>
	#include <cstdio>
	#include <vector>
	#include <algorithm>
	using namespace std;

	class Node {
	public :
	int location;
	int p, l, r;
	Node() {};
	};

	class Point {
	public:
	int id, x, y;
	Point() {};
	Point(int id, int x, int y) :id(id), x(x), y(y) {};
	bool operator < (const Point &p) const {
	return id < p.id;
	}

	void print() {
	printf("%d\n", id);
	}

	};

	const int maxx = 1000010;
	const int NIL = -1;

	int n;
	Point p[maxx];
	Node T[maxx];
	int np;

	bool lessX(const Point &p1, const Point &p2) { return p1.x < p2.x; }
	bool lessY(const Point &p1, const Point &p2) { return p1.y < p2.y; }

	int makeKDTree(int l, int r, int depth) {
	if (l >= r)
	return NIL;
	int mid = (l + r) / 2;
	int t = np++;
	if (depth % 2 == 0)
	sort(p + l, p + r, lessX);
	else
	sort(p + l, p + r, lessY);

	T[t].location = mid;
	T[t].l = makeKDTree(l, mid, depth + 1);
	T[t].r = makeKDTree(mid + 1, r, depth + 1);

	return t;
	}

	void find(int v, int sx, int tx, int sy, int ty, int depth, vector<Point> &ans) {
	int x = p[T[v].location].x;
	int y = p[T[v].location].y;

	if (sx <= x && x <= tx && sy <= y && y <= ty)
	ans.push_back(p[T[v].location]);

	if (depth % 2 == 0) {
	if (T[v].l != NIL && sx <= x)
	find(T[v].l, sx, tx,sy, ty, depth + 1, ans);
	if (T[v].r != NIL && x <= tx)
	find(T[v].r, sx, tx, sy, ty, depth + 1, ans);
	}else {
	if (T[v].l != NIL && sy <= y)
	find(T[v].l, sx, tx, sy, ty, depth + 1, ans);
	if (T[v].r != NIL && y <= ty)
	find(T[v].r, sx, tx, sy, ty, depth + 1, ans);
	}
	}
	int main()
	{
	int x, y;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
	scanf("%d %d", &x, &y);
	p[i] = Point(i, x, y);
	T[i].l = T[i].r = T[i].p = NIL;
	}

	np = 0;
	int root = makeKDTree(0, n, 0);

	int q;
	int sx, tx, sy, ty;
	vector<Point> ans;
	scanf("%d", &q);
	for (int i = 0; i < q; i++) {
	scanf("%d %d %d %d", &sx, &tx, &sy, &ty);
	ans.clear();
	find(root, sx, tx, sy, ty, 0, ans);
	sort(ans.begin(), ans.end());
	for (int j = 0; j < ans.size(); j++)
	ans[j].print();
	printf("\n");
	}
	return 0;
	}

	#include <iostream>
	#include <cstdio>
	#include <vector>
	#include <algorithm>
	using namespace std;
	typedef long long LL;
	const int maxx = 110;
	const LL INF = (1LL << 32);

	int n,q;
	LL d[maxx][maxx];

	void floyd() {
	for (int k = 0; k < n; k++) {
	for (int i = 0; i < n; i++) {
	if (d[i][k] == INF)
	continue;
	for (int j = 0; j < n; j++) {
	if (d[k][j] == INF)
	continue;
	d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
	}
	}
	}
	}
	int main()
	{
	int u, v, c;
	scanf("%d %d", &n, &q);

	for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++)
	d[i][j] = i == j ? 0 : INF;
	}

	// 输入权值
	for (int i = 0; i < q; i++) {
	scanf("%d %d %d", &u, &v, &c);
	d[u][v] = c;
	}

	floyd();

	// 判断是否存在负环
	bool negative = false;
	for (int i = 0; i < n; i++)
	if (d[i][i] < 0)
	negative = true;

	if (negative)
	printf("NEGATIVE CYCLE\n");
	else {
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
	if (d[i][j] == INF)
	printf("INF");
	else
	printf("%d", d[i][j]);
	printf("%c", j == n - 1 ? '\n' : ' ');
	}
	}
	}
	return 0;
	}

	#include <iostream>
	#include <cstdio>
	#include <vector>
	#include <queue>
	#include <list>
	#include <algorithm>
	using namespace std;
	const int maxx = 100010;
	const int INF = 1 << 30;

	vector<int>G[maxx];
	list<int>out;
	bool flag[maxx];
	int n;
	int indeg[maxx];

	void bfs(int s) {
	queue<int> q;
	q.push(s);

	while (!q.empty()) {
	int u = q.front(); q.pop();
	out.push_back(u);
	for (int i = 0; i < G[u].size(); i++) {
	int v = G[u][i];
	indeg[v]--;
	if (indeg[v] == 0 && flag[v] == 0) {
	flag[v] = true;
	q.push(v);
	}
	}
	}
	}

	void tsort() {
	for (int i = 0; i < n; i++) {
	indeg[i] = 0;
	flag[i] = false;
	}

	for (int u = 0; u < n; u++) {
	for (int i = 0; i < G[u].size(); i++) {
	int v = G[u][i];
	indeg[v]++;
	}
	}


	for (int u = 0; u < n; u++) {
	if (indeg[u] == 0 && flag[u] == 0)
	bfs(u);
	}

	for (list<int>::iterator it = out.begin(); it != out.end(); it++)
	printf("%d\n", *it);
	}
	int main()
	{
	int s, t, m;
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
	scanf("%d %d", &s, &t);
	G[s].push_back(t);
	}

	tsort();
	return 0;
	}

	#include<cstdio>
	#include<vector>
	#include<algorithm>
	using namespace std;
	const int maxx = 100010;
	int n, m, order = 0;
	int low[maxx], dfn[maxx], father[maxx], son[maxx];
	//father: 父结点 son: 子结点个数
	vector<int> cutpoint, edge[maxx];
	vector< pair<int, int> > cutedge;

	void tarjan(int u)
	{
	dfn[u] = low[u] = ++order;
	bool flag = false;
	for (int i = 0; i<edge[u].size(); i++)
	{
	int v = edge[u][i];
	if (!dfn[v])
	{
	son[u]++;
	father[v] = u;
	tarjan(v);
	if (low[v] >= dfn[u]) flag = true;
	// 点 u 为割点
	if (low[v]>dfn[u]) cutedge.push_back(make_pair(min(v, u), max(v, u)));
	// 边 v-u 为割边
	low[u] = min(low[u], low[v]);
	}
	else if (v != father[u]) low[u] = min(low[u], dfn[v]);
	}
	// 根节点若有两棵或两棵以上的子树则该为割点
	// 非根节点若所有子树节点均没有指向 u 的祖先节点的回边则为割点
	if ((father[u] == 0 && son[u]>1) \|\| (father[u] && flag)) cutpoint.push_back(u);
	}

	int main()
	{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++)
	{
	int u, v;
	scanf("%d%d", &u, &v);
	edge[u+1].push_back(v+1), edge[v+1].push_back(u+1);
	}
	tarjan(1);
	sort(cutedge.begin(), cutedge.end());
	sort(cutpoint.begin(), cutpoint.end());

	int len = cutpoint.size();
	for (int i = 0; i< len; i++)
	printf("%d\n", cutpoint[i]-1);
	return 0;
	}

	#include <iostream>
	#include <cstdio>
	#include <vector>
	#include <queue>
	using namespace std;
	const int maxx = 100010;
	const int INF = 1 << 30;

	class Edge {
	public:
	int t, w;
	Edge() {};
	Edge(int t ,int w):t(t), w(w) {};
	};
	vector<Edge> G[maxx];
	int n, d[maxx];
	bool vis[maxx];
	int cnt;

	void bfs(int s) {
	for (int i = 0; i < n; i++)
	d[i] = INF;
	queue<int> Q;
	Q.push(s);
	d[s] = 0;

	while (!Q.empty()) {
	int u = Q.front(); Q.pop();
	int len = G[u].size();
	for (int i = 0; i < len; i++) {
	Edge e = G[u][i];
	if (d[e.t] == INF) {
	d[e.t] = d[u] + e.w;
	Q.push(e.t);
	}
	}

	}

	}

	void solve() {
	// 从任选的结点 s 出发，选择距离 s 最远的结点 tgt
	bfs(0);

	int maxv = 0, tgt = 0;
	for (int i = 0; i < n; i++) {
	if (d[i] == INF)
	continue;
	if (maxv < d[i]) {
	maxv = d[i];
	tgt = i;
	}
	}


	// 从 tgt 出发，求结点 tgt 到最远结点的距离 maxv
	bfs(tgt);
	maxv = 0;
	for (int i = 0; i < n; i++) {
	if (d[i] == INF)
	continue;
	maxv = max(maxv, d[i]);
	}
	printf("%d\n", maxv);
	}
	int main() {

	int s, t, w;
	scanf("%d", &n);
	for (int i = 0; i < n - 1; i++) {
	scanf("%d %d %d", &s, &t, &w);
	// 无向图
	G[s].push_back(Edge(t, w));
	G[t].push_back(Edge(s, w));
	}
	solve();
	return 0;
	}

	#include <iostream>
	#include <cstdio>
	#include <algorithm>
	#include <vector>
	#include <queue>
	using namespace std;
	const int maxx = 100010;
	const int INF = 1 << 30;

	class DisjointSet {
	public:
	//rank 记录树的高度
	vector<int> rank, p;
	DisjointSet() {};
	DisjointSet(int size) {
	rank.resize(size, 0);
	p.resize(size, 0);
	for (int i = 0; i < size; i++)
	makeSet(i);
	}
	void makeSet(int i) {
	p[i] = i;
	rank[i] = 0;
	}

	bool same(int x, int y) {
	return findSet(x) == findSet(y);
	}

	void unite(int x, int y) {
	link(findSet(x), findSet(y));
	}

	void link(int x, int y) {
	// 包含 x 的树的高度更高，则将 y 的树合并到 x 上
	if (rank[x] > rank[y])
	p[y] = x;
	else {
	p[x] = y;
	if (rank[x] == rank[y])
	rank[y]++;
	}
	}
	int findSet(int x) {
	if (x != p[x])
	p[x] = findSet(p[x]);
	return p[x];
	}
	};

	class Edge {
	public:
	int source, target, cost;
	Edge(int source = 0, int target = 0, int cost = 0) :
	source(source), target(target), cost(cost) {}
	bool operator < (const Edge &e) const {
	return cost < e.cost;
	}
	};


	int kruskal(int n, vector<Edge> edges) {
	int totalCost = 0;
	sort(edges.begin(), edges.end());

	DisjointSet dset = DisjointSet(n + 1);
	for (int i = 0; i < n; i++)
	dset.makeSet(i);

	int len = edges.size();
	for (int i = 0; i < len; i++) {
	Edge e = edges[i];
	// 判断是否会成环
	if (!dset.same(e.source, e.target)) {
	// 添加最小生成树的边
	//MST.push_back(e);
	totalCost += e.cost;
	dset.unite(e.source, e.target);
	}
	}
	return totalCost;
	}
	int main() {

	int n, m, cost;
	int source, target;
	scanf("%d %d", &n, &m);
	vector<Edge> edges;
	for (int i = 0; i < m; i++) {
	scanf("%d %d %d", &source, &target, &cost);
	edges.push_back(Edge(source, target, cost));
	}
	printf("%d\n", kruskal(n, edges));
	return 0;
	}

	#include <iostream>
	#include <cstdio>
	#include <algorithm>
	#include <vector>
	#include <queue>
	#include <cmath>
	#include <set>
	using namespace std;
	#define EPS (1e-10)
	#define equals(a,b) (fabs((a) - (b)) < EPS)

	// 点类
	class Point {
	public :
	double x, y;
	Point() {};
	Point(double x, double y) :x(x), y(y) {}

	Point operator + (Point p) { return Point(x + p.x, y + p.y); }
	Point operator - (Point p) { return Point(x - p.x, y - p.y); }
	Point operator * (double a) { return Point(x * a, y * a); }
	Point operator / (double a) { return Point(x / a, y / a); }

	bool operator < (const Point &p) const {
	return x != p.x ? x < p.x : y < p.y;
	}

	bool operator == (const Point &p) const {
	return fabs(x - p.x) < EPS && fabs(y - p.y) < EPS;
	}
	};
	// 线段类
	class Segment {
	public:
	Point p1, p2;
	Segment() {};
	Segment(Point p1, Point p2) :p1(p1), p2(p2) {};
	};

	#define BOTTOM 0
	#define LEFT 1
	#define RIGHT 2
	#define TOP 3

	class EndPoint {
	public :
	Point p;
	int seg, st; // 线段的 ID，端点的种类
	EndPoint() {}
	EndPoint(Point p, int seg, int st) :p(p), seg(seg), st(st) {}

	bool operator < (const EndPoint &ep) const {
	// 按 y 坐标升序排序
	if (p.y == ep.p.y) {
	return st < ep.st;
	}else {
	return p.y < ep.p.y;
	}
	}

	};
	EndPoint EP[2 * 1000010];

	// 线段相交问题，曼哈顿几何
	int manhattanIntersection(vector<Segment> S) {
	int n = S.size();
	// 按照端点的 y 坐标升序排序
	sort(EP, EP + (2 * n));

	set<int> BT; // 二叉搜索树
	BT.insert(10000000001); // 设置标记
	int cnt = 0;

	for (int i = 0; i < 2 * n; i++) {
	if (EP[i].st == TOP)
	BT.erase(EP[i].p.x); // 删除上端点
	else if (EP[i].st == BOTTOM)
	BT.insert(EP[i].p.x);
	else if (EP[i].st == LEFT) {
	set<int>::iterator b = BT.lower_bound(S[EP[i].seg].p1.x);
	set<int>::iterator e = BT.upper_bound(S[EP[i].seg].p2.x);

	// 加上 b 到 e 距离
	cnt += distance(b, e);
	}

	}
	return cnt;
	}
	int main() {
	vector<Segment> S;
	Segment seg;
	int n , k = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
	scanf("%lf %lf %lf %lf", &seg.p1.x, &seg.p1.y, &seg.p2.x, &seg.p2.y);
	// 调整端点 p1、p2，保证左小右大
	if (seg.p1.y == seg.p2.y) {
	if (seg.p1.x > seg.p2.x)
	swap(seg.p1, seg.p2);
	}
	else if (seg.p1.y > seg.p2.y) {
	swap(seg.p1, seg.p2);
	}

	// 将水平线段添加到端点列表
	if (seg.p1.y == seg.p2.y) {
	EP[k++] = EndPoint(seg.p1, i, LEFT);
	EP[k++] = EndPoint(seg.p2, i, RIGHT);
	}
	else { // 将垂直线段添加到端点列表
	EP[k++] = EndPoint(seg.p1, i, BOTTOM);
	EP[k++] = EndPoint(seg.p2, i, TOP);
	}
	S.push_back(seg);
	}

	printf("%d\n", manhattanIntersection(S));
	return 0;
	}

	#define EPS (1e-10)
	#define equals(a,b) (fabs((a) - (b)) < EPS)

	// 点类
	class Point {
	public :
	double x, y;
	Point() {};
	Point(double x, double y) :x(x), y(y) {}

	Point operator + (Point p) { return Point(x + p.x, y + p.y); }
	Point operator - (Point p) { return Point(x - p.x, y - p.y); }
	Point operator * (double a) { return Point(x * a, y * a); }
	Point operator / (double a) { return Point(x / a, y / a); }

	bool operator < (const Point &p) const {
	return x != p.x ? x < p.x : y < p.y;
	}

	bool operator == (const Point &p) const {
	return fabs(x - p.x) < EPS && fabs(y - p.y) < EPS;
	}
	};
	// 线段类
	class Segment {
	public:
	Point p1, p2;
	Segment() {};
	Segment(Point p1, Point p2) :p1(p1), p2(p2) {};
	};
	// 圆类
	class Circle {
	public:
	Point c;
	double r;
	Circle() {};
	Circle(Point c, double r) :c(c), r(r) {}
	};
	// 定义向量
	typedef Point Vector;
	// 定义直线
	typedef Segment Line;
	// 定义多边形
	typedef vector<Point> Polygon;

	/************************* 点、向量 **************************/

	double norm(Point p) { return p.x * p.x + p.y * p.y; }
	double abs(Point p) { return sqrt(norm(p)); }

	// 向量的内积
	double dot(Point a, Point b) {
	return a.x * b.x + a.y * b.y;
	}
	// 向量的外积
	double cross(Point a, Point b) {
	return a.x * b.y - a.y * b.x;
	}

	// 向量 a，b 是否正交 <==> 内积为 0
	bool isOrthogonal(Vector a, Vector b) {
	return equals(dot(a, b), 0.0);
	}
	bool isOrthogonal(Point a1, Point a2, Point b1, Point b2) {
	return equals(dot(a1 - a2, b1 - b2), 0.0);
	}

	// 向量 a，b 是否平行 <==> 外积为 0
	bool isParallel(Vector a, Vector b) {
	return equals(cross(a, b), 0.0);
	}
	bool isParallel(Point a1, Point a2, Point b1, Point b2) {
	return equals(cross(a1 - a2, b1 - b2), 0.0);
	}

	// 点 p 在线段 s 上的投影
	Point project(Segment s, Point p) {
	Vector base = s.p2 - s.p1;
	double r = dot(p - s.p1, base) / norm(base);
	return s.p1 + base * r ;
	}

	// 以线段 s 为对称轴与点 p 成线对称的点
	Point reflect(Segment s, Point p) {
	return p + (project(s, p) - p) * 2.0;
	}

	// 点 a 到点 b 的距离
	double getDistance(Point a, Point b) {
	return abs(a - b);
	}

	// 线段 l 和点 p 的距离
	double getDistanceLP(Line l, Point p) {
	return abs( cross(l.p2 - l.p1, p - l.p1) / abs(l.p2 - l.p1) );
	}

	// 线段 s 与点 p 的距离
	double getDistanceSP(Segment s, Point p) {
	if (dot(s.p2 - s.p1, p - s.p1) < 0.0)
	return abs(p - s.p1);
	if (dot(s.p1 - s.p2, p - s.p2) < 0.0)
	return abs(p - s.p2);
	return getDistanceLP(s, p);
	}



	/*********************** 线段 ******************************/
	// 线段 s1，s2 是否正交 <==> 内积为 0
	bool isOrthogonal(Segment s1, Segment s2) {
	return equals(dot(s1.p2 - s1.p1, s2.p2 - s2.p1), 0.0);
	}

	// 线段 s1，s2 是否平行 <==> 外积为 0
	bool isParallel(Segment s1, Segment s2) {
	return equals(cross(s1.p2 - s1.p1, s2.p2 - s2.p1), 0.0);
	}

	// 逆时针方向 ccw（Counter-Clockwise）
	static const int COUNTER_CLOCKWISE = 1;
	static const int CLOCKWISE = -1;
	static const int ONLINE_BACK = 2;
	static const int ONLINE_FRONT = -2;
	static const int ON_SEGMENT = 0;

	int ccw(Point p0, Point p1, Point p2) {
	Vector a = p1 - p0;
	Vector b = p2 - p0;
	if (cross(a, b) > EPS) return COUNTER_CLOCKWISE;
	if (cross(a, b) < -EPS) return CLOCKWISE;
	if (dot(a, b) < -EPS) return ONLINE_BACK;
	if (norm(a) < norm(b)) return ONLINE_FRONT;
	return ON_SEGMENT;
	}

	// 判断线段 p1p2 和线段 p3p4 是否相交
	bool intersect(Point p1, Point p2, Point p3, Point p4) {
	return (ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 &&
	ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0);
	}

	// 判断线段 s1 和 s2 是否相交
	bool intersect(Segment s1, Segment s2) {
	return intersect(s1.p1, s1.p2, s2.p1, s2.p2);
	}

	// 线段 s1 和线段 s2 的距离
	double getDistance(Segment s1, Segment s2) {
	// 相交
	if (intersect(s1, s2))
	return 0.0;
	return min(min(getDistanceSP(s1, s2.p1), getDistanceSP(s1, s2.p2)),
	min(getDistanceSP(s2, s1.p1), getDistanceSP(s2, s1.p2)));
	}

	// 线段 s1 与线段 s2 的交点
	Point getCrossPoint(Segment s1, Segment s2) {
	Vector base = s2.p2 - s2.p1;
	double d1 = abs(cross(base, s1.p1 - s2.p1));
	double d2 = abs(cross(base, s1.p2 - s2.p1));
	double t = d1 / (d1 + d2);
	return s1.p1 + (s1.p2 - s1.p1) * t;
	}

	/************************* 圆 **************************/

	// 圆 c 和直线 l 的交点
	pair<Point, Point> getCrossPoints(Circle c, Line l) {
	Vector pr = project(l, c.c);
	Vector e = (l.p2 - l.p1) / abs(l.p2 - l.p1);
	double base = sqrt(c.r * c.r - norm(pr - c.c));
	return make_pair(pr + e * base, pr - e * base);
	}

	// 圆 c1 和圆 c2 的交点
	double arg(Vector p) { return atan2(p.y, p.x); }
	Vector polar(double a, double r) { return Point(cos(r) * a, sin(r) * a); }

	pair<Point, Point> getCrossPoints(Circle c1, Circle c2) {
	double d = abs(c1.c - c2.c);
	double a = acos((c1.r * c1.r + d * d - c2.r * c2.r) / (2 * c1.r * d));
	double t = arg(c2.c - c1.c);
	return make_pair(c1.c + polar(c1.r, t + a), c1.c + polar(c1.r, t - a));
	}

	/************************* 多边形 **************************/
	// 点的内包
	/*
	IN 2
	ON 1
	OUT 0
	*/
	int contains(Polygon g, Point p) {
	int n = g.size();
	bool x = false;
	for (int i = 0; i < n; i++) {
	Point a = g[i] - p, b = g[(i + 1) % n] - p;
	if (abs(cross(a, b)) < EPS && dot(a, b) < EPS) return 1;
	if (a.y > b.y) swap(a, b);
	if (a.y < EPS && EPS < b.y && cross(a, b) > EPS)
	x = !x;
	}
	return (x ? 2 : 0);
	}
	int cmp(Point A, Point B) // 竖直排序
	{
	return (A.y<B.y \|\| (A.y == B.y&&A.x<B.x));
	}
	// 凸包
	Polygon andrewScan(Polygon s) {
	Polygon u, l;
	int len = s.size();
	if (len < 3) return s;


	// 以 x，y 为基准升序排序
	sort(s.begin(), s.end());
	// 将 x 值最小的两个点添加到 u
	u.push_back(s[0]);
	u.push_back(s[1]);

	// 将 x 值最大的两个点添加到 l
	l.push_back(s[len - 1]);
	l.push_back(s[len - 2]);

	// 构建凸包上部
	for (int i = 2; i < len; i++) {
	for (int j = u.size(); j >= 2 && ccw(u[j - 2], u[j - 1], s[i]) >= 0; j--) {
	u.pop_back();
	}
	u.push_back(s[i]);
	}
	// 构建凸包下部
	for (int i = len - 3; i >= 0; i--) {
	for (int j = l.size(); j >= 2 && ccw(l[j - 2], l[j - 1], s[i]) >= 0; j--) {
	l.pop_back();
	}
	l.push_back(s[i]);
	}

	reverse(l.begin(), l.end());
	for (int i = u.size() - 2; i >= 1; i--)
	l.push_back(u[i]);

	return l;
	}

	#include <iostream>
	#include <algorithm>
	#include <cstdio>
	using namespace std;
	const int INF = 1 << 30;
	int main() {
	int n, m;
	int A[100];
	int T[50000 + 10];
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++)
	scanf("%d", &A[i]);
	for (int i = 0; i <= n; i++)
	T[i] = INF;
	T[0] = 0;
	for (int i = 0; i < m; i++) {
	for (int j = A[i]; j <= n; j++)
	T[j] = min(T[j], T[j - A[i]] + 1);
	}
	printf("%d\n", T[n]);
	return 0;
	}

	#include <iostream>
	#include <algorithm>
	#include <cstdio>
	#include <cstring>
	using namespace std;
	const int INF = 1 << 30;
	const int maxx = 10010;

	int dp[maxx], s[maxx];
	int w[maxx], v[maxx];
	int main() {
	int n, W;
	int A[100];
	int T[50000 + 10];
	scanf("%d %d", &n, &W);
	memset(dp, 0, sizeof(dp));
	memset(s, 0, sizeof(s));
	for (int i = 1; i <= n; i++)
	{
	scanf("%d %d", &v[i], &w[i]);
	s[i] = s[i - 1] + w[i];
	}
	for (int i = 1; i <= n; i++)
	{
	int b = max(w[i], W - s[n] + s[i - 1]);
	for (int j = W; j >= b; j--)
	dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
	}
	printf("%d\n", dp[W]);
	return 0;
	}

	#include<iostream>
	#include<cmath>
	#include<cstdio>
	#include<cstring>
	#include<algorithm>
	using namespace std;

	const int INF = 1e9;
	int dp[110000];// 记录以 a [i] 结束的最长子序列的长度
	int a[110000];


	int main()
	{
	// freopen("in.txt","r",stdin);
	int n;
	while (scanf("%d", &n) != EOF&&n)
	{
	for (int i = 0; i<n; i++)
	dp[i] = INF;
	for (int i = 0; i<n; i++)
	scanf("%d", &a[i]);

	int len = 0;
	for (int i = 0; i<n; i++)
	{
	*lower_bound(dp, dp + n, a[i]) = a[i];
	}
	printf("%d\n", lower_bound(dp, dp + n, INF) - dp);
	}
	return 0;
	}

	#include<iostream>
	#include<cmath>
	#include<cstdio>
	#include<cstring>
	#include<algorithm>
	using namespace std;
	const int maxx = 1410;
	int dp[maxx][maxx], G[maxx][maxx];

	int getLargestSquare(int H, int W) {
	int maxWidth = 0;
	for (int i = 0; i < H; i++)
	for (int j = 0; j < W; j++) {
	dp[i][j] = (G[i][j] + 1) % 2;
	maxWidth \|= dp[i][j];
	}

	for (int i = 1; i < H; i++)
	for (int j = 1; j < W; j++) {
	if (G[i][j]) {
	dp[i][j] = 0;
	}else {
	dp[i][j] = min(dp[i - 1][j - 1],
	min(dp[i][j - 1], dp[i - 1][j]) ) + 1;
	maxWidth = max(maxWidth, dp[i][j]);
	}
	}
	return maxWidth * maxWidth;
	}
	int main()
	{
	int H, W;
	scanf("%d %d", &H, &W);
	for (int i = 0; i < H; i++)
	for (int j = 0; j < W; j++)
	scanf("%d", &G[i][j]);

	printf("%d\n", getLargestSquare(H, W));
	return 0;
	}

	#include<iostream>
	#include<cstdio>
	#include<algorithm>
	#include<stack>
	using namespace std;
	const int maxx = 1410;

	int H, W;
	int buffer[maxx][maxx];
	int T[maxx][maxx];
	struct Rectangle { int height; int pos; };

	int getLargestRectangle(int size, int height[]) {
	stack<Rectangle> S;
	int maxv = 0;
	// 使得栈顶元素必定大于最后元素，使得前面的值被计算进来
	height[size] = 0;

	for (int i = 0; i <= size; i++) {
	Rectangle rect;
	rect.height = height[i];
	rect.pos = i;
	// 当 S 为空
	if (S.empty())
	S.push(rect);
	// 栈顶的高度小于当前的高度
	else if (S.top().height < rect.height)
	S.push(rect);
	// 栈顶的高度大于当前的高度
	else if (S.top().height > rect.height) {
	int target = i;
	// 栈顶的高度大于等于当前的高度
	// 出现小于栈顶高度的代表 pre.pos~i 之间都存在高度为 pre.height 的干净瓷砖
	// 此时可以计算当前的面积
	while (!S.empty() && S.top().height >= rect.height) {
	Rectangle pre = S.top(); S.pop();
	// 长 * 宽
	int area = pre.height * (i - pre.pos);
	maxv = max(maxv, area);
	target = pre.pos;
	}
	// 加上前面的宽度（下标设置为之前的），以便后面有合适的瓷砖进行计算
	rect.pos = target;
	S.push(rect);
	}
	}
	return maxv;
	}

	int solve() {
	// 以行为直方图，计算纵向的干净长度
	for (int j = 0; j < W; j++) {
	for (int i = 0; i < H; i++) {
	if (buffer[i][j])
	T[i][j] = 0;
	else
	T[i][j] = (i > 0) ? T[i - 1][j] + 1 : 1;
	}
	}

	// 从行计算出当前行的最大面积
	int maxv = 0;
	for (int i = 0; i < H; i++)
	maxv = max(maxv, getLargestRectangle(W, T[i]));
	return maxv;
	}
	int main()
	{
	scanf("%d %d", &H, &W);
	for (int i = 0; i < H; i++)
	for (int j = 0; j < W; j++)
	scanf("%d", &buffer[i][j]);

	printf("%d\n", solve());
	return 0;
	}

	#include<iostream>
	#include<cstdio>
	using namespace std;

	int isPrime(int x) {
	if (x < 2)
	return 0;
	else if (x == 2)
	return 1;
	if (x % 2 == 0)
	return 0;
	for (int i = 3; i * i <= x; i += 2)
	if (x % i == 0)
	return 0;
	return 1;
	}
	int main()
	{
	int n, t, cnt = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
	scanf("%d", &t);
	if (isPrime(t))
	cnt++;
	}
	printf("%d\n", cnt);
	return 0;
	}

	#include<iostream>
	#include<cstdio>
	using namespace std;

	int gcd(int x, int y) {
	return y ? gcd(y, x % y): x;
	}
	int main()
	{
	int x, y;
	scanf("%d %d", &x, &y);
	printf("%d\n", gcd(x, y));
	return 0;
	}

	#include<iostream>
	#include<cstdio>
	using namespace std;
	typedef long long LL;

	LL mod_pow(LL n, LL m, LL mod) {
	LL res = 1;
	while (m > 0) {
	if (m & 1)
	res = res * n % mod;
	n = n * n % mod;
	m >>= 1;
	}
	return res;
	}
	int main()
	{
	LL n, m;
	LL mod = 1000000007;
	scanf("%lld %lld", &n, &m);
	printf("%d\n", mod_pow(n, m , mod));
	return 0;
	}

	#include<iostream>
	#include<cstdio>
	#include<algorithm>
	#include<stack>
	using namespace std;
	const int maxx = 8;
	// 行列、斜列
	int row[maxx], col[maxx];
	int dpos[maxx * 2 - 1], dneg[maxx * 2 - 1];

	int x[maxx][maxx];

	void init() {
	for (int i = 0; i < maxx; i++)
	row[i] = col[i] = 0;
	for (int i = 0; i < maxx * 2 - 1; i++)
	dpos[i] = dneg[i] = 0;
	for (int i = 0; i < maxx; i++)
	for (int j = 0; j < maxx; j++)
	x[i][j] = 0;
	}
	void print() {

	for (int i = 0; i < maxx; i++) {
	for (int j = 0; j < maxx; j++) {
	if (x[i][j] && row[i] != j)
	return;
	}
	}
	for (int i = 0; i < maxx; i++) {
	for (int j = 0; j < maxx; j++) {
	printf("%c", row[i] == j ? 'Q' : '.');
	}
	printf("\n");
	}
	}
	void recursive(int i) {
	if (i == maxx) {
	print();
	return;
	}

	for (int j = 0; j < maxx; j++) {
	// 不适合放在这里
	if (col[j] \|\| dpos[i + j] \|\| dneg[i - j + maxx - 1])
	continue;

	// 尝试放下这里
	row[i] = j; col[j] = dpos[i + j] = dneg[i - j + maxx - 1] = 1;
	recursive(i + 1);
	// 恢复刚才的操作继续其他的操作
	row[i] = col[j] = dpos[i + j] = dneg[i - j + maxx - 1] = 0;
	}
	}
	int main()
	{
	int k;
	int r, c;
	scanf("%d", &k);
	for (int i = 0; i < k; i++){
	scanf("%d %d", &r, &c);
	x[r][c] = 1;
	}

	recursive(0);
	return 0;
	}

	#include<iostream>
	#include<cstdio>
	#include<algorithm>
	#include<queue>
	#include<map>
	#include<string>
	using namespace std;
	const int row = 3;
	const int maxx = 9;

	struct Puzzle {
	int f[maxx];
	int space;
	string path;
	bool operator < (const Puzzle &p) const {
	for (int i = 0; i < maxx; i++) {
	if (f[i] != p.f[i])
	return f[i] > p.f[i];
	}
	return false;
	}
	};

	const int dx[4] = { -1, 0, 1, 0 };
	const int dy[4] = { 0, -1, 0 ,1 };
	const char dir[4] = { 'u','l','d','r' };

	bool isTarget(Puzzle p) {
	for (int i = 0; i < maxx; i++)
	if (p.f[i] != (i + 1))
	return false;
	return true;
	}


	string bfs(Puzzle s) {
	queue<Puzzle> Q;
	map<Puzzle, bool> V;
	Puzzle u, v;
	s.path = "";
	Q.push(s);
	V[s] = true;

	while (!Q.empty()) {
	u = Q.front(); Q.pop();
	if (isTarget(u))
	return u.path;
	int sx = u.space / row;
	int sy = u.space % row;
	for (int r = 0; r < 4; r++) {
	int tx = sx + dx[r];
	int ty = sy + dy[r];

	if (tx < 0 \|\| ty < 0 \|\| tx >= row \|\| ty >= row)
	continue;
	v = u;
	swap(v.f[u.space], v.f[tx * row + ty]);
	v.space = tx * row + ty;
	if (!V[v]) {
	V[v] = true;
	v.path += dir[r];
	Q.push(v);
	}
	}
	}
	return "unsolveable";
	}
	int main()
	{
	Puzzle in;
	for (int i = 0; i < maxx; i++) {
	cin >> in.f[i];
	if (in.f[i] == 0) {
	in.f[i] = maxx;
	in.space = i;
	}
	}
	string ans = bfs(in);
	printf("%d\n", ans.size());
	return 0;
	}

	/IDA 算法 */
	#include<iostream>
	#include<cstdio>
	#include<algorithm>
	#include<queue>
	#include<map>
	#include<string>
	using namespace std;
	const int row = 4;
	const int maxx = 16;
	const int LIMIT = 100;
	struct Puzzle {
	int f[maxx], space, MD;
	};

	const int dx[4] = { 0, -1, 0, 1 };
	const int dy[4] = { 1, 0, -1 ,0 };
	const char dir[4] = { 'r','u','l','d' };
	int MDT[maxx][maxx];

	Puzzle state;
	int limit;
	int path[LIMIT];

	int getAllMD(Puzzle pz) {
	int sum = 0;
	for (int i = 0; i < maxx; i++) {
	if (pz.f[i] != maxx)
	sum += MDT[i][pz.f[i] - 1];
	}
	return sum;
	}

	bool isSolved() {
	for (int i = 0; i < maxx; i++)
	if (state.f[i] != i + 1)
	return false;
	return true;
	}

	bool dfs(int depth, int prev) {

	if (state.MD == 0)
	return true;

	// 如果当前的深度加上启发值超过了限制，则进行剪枝
	if (depth + state.MD > limit)
	return false;

	int sx = state.space / row;
	int sy = state.space % row;

	Puzzle tmp;
	for (int r = 0; r < 4; r++) {
	int tx = sx + dx[r];
	int ty = sy + dy[r];
	if (tx < 0 \|\| ty < 0 \|\| tx >= row \|\| ty >= row)
	continue;
	if (max(prev, r) - min(prev, r) == 2)
	continue;
	tmp = state;
	// 计算曼哈顿距离的差值，同时交换拼图
	state.MD -= MDT[tx * row + ty][state.f[tx * row + ty] - 1];
	state.MD += MDT[sx * row + sy][state.f[tx * row + ty] - 1];
	swap(state.f[tx * row + ty], state.f[sx * row + sy]);
	state.space = tx * row + ty;
	if (dfs(depth + 1, r)) {
	path[depth] = r;
	return true;
	}
	state = tmp;
	}
	return false;
	}

	string iterative_deepening(Puzzle in) {
	// 初始状态的曼哈顿距离
	in.MD = getAllMD(in);
	for (limit = in.MD; limit <= LIMIT; limit++) {
	state = in;
	if (dfs(0, -100)) {
	string ans = "";
	for (int i = 0; i < limit; i++)
	ans += dir[path[i]];
	return ans;
	}
	}
	return "unsolvable";
	}

	int main()
	{
	for (int i = 0; i < maxx; i++) {
	for (int j = 0; j < maxx; j++) {
	MDT[i][j] = abs(i / row - j / row) + abs(i % row - j % row);
	}
	}
	Puzzle in;
	for (int i = 0; i < maxx; i++) {
	cin >> in.f[i];
	if (in.f[i] == 0) {
	in.f[i] = maxx;
	in.space = i;
	}
	}
	string ans = iterative_deepening(in);
	printf("%d\n", ans.size());
	return 0;
	}

	/A 算法 */
	#include<iostream>
	#include<cstdio>
	#include<algorithm>
	#include<queue>
	#include<map>
	#include<string>
	using namespace std;
	const int row = 4;
	const int maxx = 16;
	const int LIMIT = 100;
	struct Puzzle {
	int f[maxx], space, MD;
	int cost;
	bool operator < (const Puzzle &p) const {
	for (int i = 0; i < maxx; i++) {
	if (f[i] != p.f[i])
	return f[i] < p.f[i];
	}
	return false;
	}
	};

	struct State {
	Puzzle puzzle;
	int estimated;
	bool operator < (const State &s) const {
	return estimated > s.estimated;
	}
	};
	const int dx[4] = { 0, -1, 0, 1 };
	const int dy[4] = { 1, 0, -1 ,0 };
	const char dir[4] = { 'r','u','l','d' };
	int MDT[maxx][maxx];


	int getAllMD(Puzzle pz) {
	int sum = 0;
	for (int i = 0; i < maxx; i++) {
	if (pz.f[i] != maxx)
	sum += MDT[i][pz.f[i] - 1];
	}
	return sum;
	}

	int astar(Puzzle s) {

	priority_queue<State> PQ;
	s.MD = getAllMD(s);
	s.cost = 0;
	map<Puzzle, bool> V;
	Puzzle u, v;
	State initial;
	initial.puzzle = s;
	initial.estimated = getAllMD(s);
	PQ.push(initial);

	while (!PQ.empty()) {
	State st = PQ.top(); PQ.pop();
	u = st.puzzle;
	if (u.MD == 0)
	return u.cost;
	V[u] = true;
	int sx = u.space / row;
	int sy = u.space % row;
	for (int r = 0; r < 4; r++) {
	int tx = sx + dx[r];
	int ty = sy + dy[r];
	if (tx < 0 \|\| ty < 0 \|\| tx >= row \|\| ty >= row)
	continue;
	v = u;
	// 计算曼哈顿距离的差值，同时交换拼图
	v.MD -= MDT[tx * row + ty][v.f[tx * row + ty] - 1];
	v.MD += MDT[sx * row + sy][v.f[tx * row + ty] - 1];

	swap(v.f[tx * row + ty], v.f[sx * row + sy]);
	v.space = tx * row + ty;
	if (!V[v]) {
	v.cost++;
	State news;
	news.puzzle = v;
	news.estimated = v.cost + v.MD;
	PQ.push(news);
	}
	}
	}

	return -1;
	}


	int main()
	{
	for (int i = 0; i < maxx; i++) {
	for (int j = 0; j < maxx; j++) {
	MDT[i][j] = abs(i / row - j / row) + abs(i % row - j % row);
	}
	}
	Puzzle in;
	for (int i = 0; i < maxx; i++) {
	cin >> in.f[i];
	if (in.f[i] == 0) {
	in.f[i] = maxx;
	in.space = i;
	}
	}

	printf("%d\n", astar(in));
	return 0;
	}

# 高等数据结构

# 并差集

# kd 树

# 图进阶

# 所有点对间最短路径

# 拓扑排序

# 关节点

# 树的直径

# 最小生成树

# 几何学

# 动态规划

# 硬币问题

# 背包问题

# 最长递增子序列

# 最大正方形

# 最大长方形

# 数论

# 质数

# 最大公约数

# 幂乘

# 启发式搜索

# 八皇后问题

# 九宫格拼图

# 十六格拼图

# 高等数据结构

# 并差集

# kd 树

# 图进阶

# 所有点对间最短路径

# 拓扑排序

# 关节点

# 树的直径

# 最小生成树

# 几何学

# 动态规划

# 硬币问题

# 背包问题

# 最长递增子序列

# 最大正方形

# 最大长方形

# 数论

# 质数

# 最大公约数

# 幂乘

# 启发式搜索

# 八皇后问题

# 九宫格拼图

# 十六格拼图

挑战程序竞赛2上

数据结构