제출 #119596

#제출 시각아이디문제언어결과실행 시간메모리
119596davitmargTriangles (CEOI18_tri)C++17
35 / 100
1006 ms138488 KiB
/*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

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(6498465);
	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;
}


/*


4
5 10
0 0
4 3
10 0



*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...