제출 #119552

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
119552		davitmarg	Triangles (CEOI18_tri)	C++17	0 / 100	2 ms	384 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

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 convex(vector<int> p)
{
	vector<int> up, down;
	vector<bool> uUp(p.size() + 5), uDown(p.size() + 5);
	int st, en;

	st = p[0];
	en = p.back();

	reverse(all(p));
	p.pop_back();
	reverse(all(p));
	p.pop_back();

	vector<int> add = p;
	
	p.clear();
	p.PB(st);
	for (int i = 0; i < add.size(); i++)
	{
		random_shuffle(all(add));
		for (int j = 0; j < add.size(); j++)
			p.PB(add[j]);
	}

	p.PB(en);
	up.PB(p[0]);
	down.PB(p[0]);
	for (int i = 1; i < p.size(); i++)
	{
		if (i == p.size() - 1 || (!uUp[p[i]] && cw(st, p[i], en)))
		{
			while (up.size() > 1 && !cw(up[up.size() - 2], up[up.size() - 1], p[i]))
			{
				uUp[up.back()] = 0;
				up.pop_back();
			}
			up.PB(p[i]);
			uUp[up.back()] = 1;
		}

		if (i == p.size() - 1 || (!uDown[p[i]] && ccw(st, p[i], en)))
		{
			while (down.size() > 1 && !ccw(down[down.size() - 2], down[down.size() - 1], p[i]))
			{
				uDown[down.back()] = 0;
				down.pop_back();
			}
			down.PB(p[i]);
			uDown[down.back()] = 1;
		}
	}

	for (int i = 1; i < up.size() - 1; i++)
		for (int j = 1; j < down.size() - 1; j++)
			if (!cw(up[i], en, down[j]) || !ccw(up[i], st, down[i]))
				return 0;

	down.pop_back();
	reverse(all(down));
	down.pop_back();
	reverse(all(down));
	while (!down.empty())
	{
		up.PB(down.back());
		down.pop_back();
	}
	
	/*for (int i = 0; i < up.size(); i++)
		for (int j = i + 1; j < up.size(); j++)
			for (int k = 0; k < up.size(); k++)
			{
				if (k == i || k == j)
					continue;
				if (ccw(up[i], up[k], up[j]) == (i < k && k < j))
					return 0;
			}*/

	return up.size();
}

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


	for (int i = 1; i <= n; i++)
		p.PB(i);
	//random_shuffle(all(p));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			if (i == j)
				continue;
			swap(p[0], p[i]);
			swap(p.back(), p[j]);
			ans = max(ans, convex(p));
			swap(p[0], p[i]);
			swap(p.back(), p[j]);
		}
	give_answer(ans);
	return 0;
}


/*


4
0 0
5 10
10 0
5 5



*/

컴파일 시 표준 에러 (stderr) 메시지

tri.cpp: In function 'int convex(std::vector<int>)':
tri.cpp:91:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < add.size(); i++)
                  ~~^~~~~~~~~~~~
tri.cpp:94:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < add.size(); j++)
                   ~~^~~~~~~~~~~~
tri.cpp:101:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < p.size(); i++)
                  ~~^~~~~~~~~~
tri.cpp:103:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i == p.size() - 1 || (!uUp[p[i]] && cw(st, p[i], en)))
       ~~^~~~~~~~~~~~~~~
tri.cpp:114:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i == p.size() - 1 || (!uDown[p[i]] && ccw(st, p[i], en)))
       ~~^~~~~~~~~~~~~~~
tri.cpp:126:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < up.size() - 1; i++)
                  ~~^~~~~~~~~~~~~~~
tri.cpp:127:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 1; j < down.size() - 1; j++)
                   ~~^~~~~~~~~~~~~~~~~

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