Submission #120104

#	Time	Username	Problem	Language	Result	Execution time	Memory
120104		davitmarg	Triangles (CEOI18_tri)	C++17	35 / 100	114 ms	31924 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>

#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

bitset<502> is, used[502][502], pre[502][502];

bool cw(int a, int b, int c)
{
	if (used[a][b][c])
		return pre[a][b][c];

	used[a][b][c] = 1;
	used[b][c][a] = 1;
	used[c][a][b] = 1;

	used[c][b][a] = 1;
	used[a][c][b] = 1;
	used[b][a][c] = 1;


	pre[a][b][c] = pre[c][a][b] = pre[b][c][a] = is_clockwise(a, b, c);
	pre[c][b][a] = pre[b][a][c] = pre[a][c][b] = !pre[a][b][c];
	return pre[a][b][c];
}
bool ccw(int a, int b, int c)
{
	return !cw(a, b, c);
}

int ans, n,d[40002];
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(1);
	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;
			if(d[i]==2 || d[j]==2)
                continue;

			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);
			d[i]+=(sum == n - 2 || sum == 0);
			d[j]+=(sum == n - 2 || sum == 0);
		}

	give_answer(ans);

	return 0;
}


/*


4
5 10
0 0
4 3
10 0



*/

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