Submission #119589

#	Time	Username	Problem	Language	Result	Execution time	Memory
119589		Abelyan	Triangles (CEOI18_tri)	C++17	55 / 100	1858 ms	262144 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;
 
#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)
{
	
	pair<LL, LL> A, B, C;
	A = point[a];
	B = point[b];
	C = point[c];
	return A.first * (B.second - C.second) + B.first * (C.second - A.second) + C.first * (A.second - B.second) < 0;
}
 
void give_answer(int x)
{
	cout << x << endl;
}
 
#endif // death
 
map<pair<int, pair<int, int>>, bool> used, pre;
 
bool cw(int a, int b, int c)
{
	if (used[MP(a, MP(b, c))])
		return pre[MP(a, MP(b, c))];
	used[MP(a, MP(b, c))] = 1;
	return pre[MP(a, MP(b, c))] = is_clockwise(a, b, c);
}
 
bool ccw(int a, int b, int c)
{
	return !cw(a, b, c);
}
 
int ans, n;
vector<int> p;
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;
		point.PB(MP(x,y));
	}
#endif // death
	srand(6465);
	for (int i = 0; i < n; i++)
		p.PB(i+1);
	random_shuffle(all(p));
	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)
		{
			int sum = 0;
			int cnt = 0;
			for (int k = 0; k < n; k++)
			{
				if (k == i || k == j)
					continue;
				cnt++;
				sum += cw(p[i],p[k], p[j]);
				if (sum && sum != cnt)
					break;
			}
			ans += (sum == n - 2 || sum == 0);
		}
 
	give_answer(ans);
 
	return 0;
}
 

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