Submission #168992

#	Time	Username	Problem	Language	Result	Execution time	Memory
168992		kostia244	Triangles (CEOI18_tri)	C++17	0 / 100	3 ms	632 KiB

tri

#include<bits/stdc++.h>
#include "trilib.h"
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using namespace std;
using ll = long long;
using vi = vector<int>;
const int mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
namespace local {
	int p = -1;
	using vec = complex<int>;
	int cross(vec a, vec b) {
		return (conj(a)*b).imag();
	}
	vector<vec> v;
	int N;
	int get_n() {
		cin >> N;
//		N = 20;
		v.resize(N);
		for(auto &i : v) {
			int x, y;
			cin >> x >> y;
//			x = rng()%100, y = rng()%100;
			i = vec(x, y);
		}
		return N;
	}
	void give_answer(int x) {
		if(p!=-1&&p!=x) {
			cout << "WA\n";
			cout << N << "\n";
			for(auto i : v)
				cout << i.real() << " " << i.imag() << "\n";
		}
		cout << "ANSWER:" << x << "\n";
		p=x;
	}
	bool is_clockwise(int a, int b, int c) {
//		cerr << a << " " << b << " " << c << "\n";
		if(a!=b&&b!=c&&c!=a)
		assert(cross(v[b-1]-v[a-1], v[c-1]-v[a-1]));
		return cross(v[b-1]-v[a-1], v[c-1]-v[a-1])>0;
	}
}
// using namespace local;
int n;
int check(int a) {
	int b = 1+(a==1);
	for(int i = 1; i <= n; i++)
		if(i!=a&&i!=b&&is_clockwise(a, b, i))
			b = i;
	for(int i = 1; i <= n; i++)
		if(i!=a&&i!=b&&is_clockwise(a, b, i))
			return 0;
	return 1;
}
vi hull(vi v, int V) {
    sort(all(v), [&](const int& a, const int &b) {
		return !is_clockwise(V, a, b);
	});
	vi hull = {V};
	for(auto i : v) {
		while(hull.size()>1&&is_clockwise(hull[hull.size()-2], hull.back(), i))
			hull.pop_back();
		hull.pb(i);
	}
	return hull;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	n = get_n();
	vi a[2];
	a[0].pb(2);
	for(int i = 3; i <= n; i++) a[is_clockwise(1, 2, i)].pb(i);
	vi x = hull(a[0], 1), y = hull(a[1], 1);
	#define a x
	#define b y
    reverse(all(y));//0 = top, 1 = bottom
    while(a.size()&&b.size()) {
        if(a.size()==1&&b.size()==1) break;
        int A = a.size(), B = b.size();
        if(A>1&&is_clockwise(a[A-2], a[A-1], b[B-1])) {
            a.pop_back();
        }else 
        if(B>1&&is_clockwise(a[A-1], b[B-1], b[B-2])) {
            b.pop_back();
        } else break;
    }
    reverse(all(x)), reverse(all(y));
    while(a.size()&&b.size()) {
        if(a.size()==1&&b.size()==1) break;
        int A = a.size(), B = b.size();
        if(A>1&&!is_clockwise(a[A-2], a[A-1], b[B-1])) {
            a.pop_back();
        }else
        if(B>1&&!is_clockwise(a[A-1], b[B-1], b[B-2])) {
            b.pop_back();
        }else break;
    }
    give_answer(a.size()+b.size());
}

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