제출 #119616

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
119616		davitmarg	Triangles (CEOI18_tri)	C++17	100 / 100	64 ms	3820 KiB

tri

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define death
#ifndef death
#include<trilib.h>
#endif // death

#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;


struct pt
{
	LL x, y;
	pt(LL X = 0, LL Y = 0)
	{
		x = X;
		y = Y;
	}
};

#ifdef death

int get_n()
{
	int x;
	cin >> x;
	return x;
}

vector<pair<LL, LL>> point;

bool is_clockwise(int a, int b, int c)
{
	return 0;
}

void give_answer(int x)
{
	cout << x << endl;
}

#endif // death

map<pair<int, pair<int, int>>, bool> used, pre;

bool cw(pt a, pt b, pt c) {
	return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) < 0;
}

bool ccw(pt a, pt b, pt c) {
	return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) > 0;
}

int ans, n;
vector<pt> p;

int convex_hull(vector<pt> a) {
	sort(a.begin(), a.end(), [](pt a, pt b) {
		if (a.x == b.x)
			return a.x < b.x;
		return a.y < b.y;
	});
	pt p1 = a[0], p2 = a.back();
	vector<pt> up, down;
	up.push_back(p1);
	down.push_back(p1);
	for (size_t i = 1; i < a.size(); ++i) {
		if (i == a.size() - 1 || cw(p1, a[i], p2)) {
			while (up.size() >= 2 && !cw(up[up.size() - 2], up[up.size() - 1], a[i]))
				up.pop_back();
			up.push_back(a[i]);
		}
		if (i == a.size() - 1 || ccw(p1, a[i], p2)) {
			while (down.size() >= 2 && !ccw(down[down.size() - 2], down[down.size() - 1], a[i]))
				down.pop_back();
			down.push_back(a[i]);
		}
	}
	a.clear();
	for (size_t i = 0; i < up.size(); ++i)
		a.push_back(up[i]);
	for (size_t i = down.size() - 2; i > 0; --i)
		a.push_back(down[i]);
	return a.size();
}

int main()
{
	n = get_n();

#ifdef death
	point.PB(MP(0, 0));
	for (int i = 0; i < n; i++)
	{
		LL x, y;
		cin >> x >> y;
		p.PB(pt(x, y));
	}
#endif // death

	ans = convex_hull(p);

	give_answer(ans);

	return 0;
}


/*


4
5 10
0 0
4 3
10 0



*/

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 25 / 25