【CZY选讲·黑白染色】

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题目描述

给出平面上n 个点，试将他们黑白染色，要求染色后无法用一条直线把黑白完全分开。 随便输出一种方案。

数据范围

n<=100000

题解：

①点数很多，但是可以发现至多需要4个点就可以完成。

②根据上述结论进行分类讨论即可：

找三个点，若三点共线，则按图1方法染色。

若三点不共线，再找第四个点，若与其中两点共线，则按图2方法染色。

若第四个点在三角形外，则按图3方式染色。

若第四个点在三角形内，则按图4方式染色。

#include<stdio.h>

#include<algorithm>

#include<iostream>

#include<math.h>

#include<cstring>

#define go(i,a,b) for(int i=a;i<=b;i++)

#define ro(i,a,b) for(int i=a;i>=b;i--)

#define fo(i,a,x) for(int i=a[x],v=e[i].v;i;i=e[i].next,v=e[i].v)

#define mem(a,b) memset(a,b,sizeof(a))

using namespace std;

int main()

{

        //某大神口糊的题,暂时没有代码

	return 0;

}//czy020202