atcoder #082 E 暴力 计算几何

给出点集，然后求一个凸包的所有的子凸包的贡献总和，贡献计算是凸包内部含边界上点的数量N，凸包的不包含边界的顶点数S，贡献为$2^{N-S}$

首先很容易想到，凸包上包含内部的所有点构成的子凸包有Sum(i = 3 ->N)C(i,N)种情况，这个式子其实就是二项式的一部分。但是有可能出现多点共线的不合法情况，所以问题转换为求所有点构成的直线中，每条直线上大于2点的点的数目，每条直线都要分别计算，最后减去就行了。求共线可以用叉积可以用斜率，注意判重。

这场比赛迟了10分钟才写，这题开始还在用凸包搞，简直蠢(

/** @Date    : 2017-09-02 20:30:47
  * @FileName: C.cpp
  * @Platform: Windows
  * @Author  : Lweleth (SoungEarlf@gmail.com)
  * @Link    : https://github.com/
  * @Version : $Id$
  */
#include <bits/stdc++.h>
#define LL long long
#define PII pair<int ,int>
#define MP(x, y) make_pair((x),(y))
#define fi first
#define se second
#define PB(x) push_back((x))
#define MMG(x) memset((x), -1,sizeof(x))
#define MMF(x) memset((x),0,sizeof(x))
#define MMI(x) memset((x), INF, sizeof(x))
using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 210;
const double eps = 1e-6;
const LL mod = 998244353;

LL fa[210], inv[210];

LL fpow(LL a, LL n)
{
    LL r = 1LL;
    while(n > 0)
    {
        if(n & 1)
            r = r * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return r;
}

void init()
{
    fa[0] = 1;
    inv[0] = 1;
    for(LL i = 1; i <= 200; i++)
    {
        fa[i] = fa[i-1] * i % mod;
        inv[i] = fpow(fa[i], mod - 2);
    }
}

LL C(LL n, LL m)
{
    if(n < 0)
        return 0;
    n >>= 1;
    if(n == 0)
    	return 1LL;
    LL ans = 0;
    ans = ((fa[n + m] * inv[m] % mod)* inv[n]) % mod;
    return ans;
}


struct point
{
	double x, y;
	point(){}
	point(double _x, double _y){x = _x, y = _y;}
	point operator -(const point &b) const
	{
		return point(x - b.x, y - b.y);
	}
	double operator *(const point &b) const 
	{
		return x * b.x + y * b.y;
	}
	double operator ^(const point &b) const
	{
		return x * b.y - y * b.x;
	}
	bool operator == (const point &b) const
	{
		return x==b.x && y==b.y;
	}
	
};

double xmult(point p1, point p2, point p0)  
{  
    return (p1 - p0) ^ (p2 - p0);  
}  

double distc(point a, point b)
{
	return sqrt((double)((b - a) * (b - a)));
}
int sign(double x)
{
	if(fabs(x) < eps)
		return 0;
	if(x < 0)
		return -1;
	else 
		return 1;
}

struct line
{
	point s, t;
	line(){}
	line(point ss, point tt){
		s = ss, t = tt;
	}
};

////////
int n;
point stk[N];
point p[N];

int cmpC(point a, point b)//水平序排序
{
	return sign(a.x - b.x) < 0 || (sign(a.x - b.x) == 0 && sign(a.y - b.y) < 0);
}

int Graham()//水平序
{
	sort(p, p + n, cmpC);
	int top = 0;
	for(int i = 0; i < n; i++)
	{
		while(top >= 2 && sign(xmult(stk[top - 2], stk[top - 1], p[i])) < 0)
			top--;
		stk[top++] = p[i];
	}
	int tmp = top;
	for(int i = n - 2; i >= 0; i--)
	{
		while(top > tmp && sign(xmult(stk[top - 2],stk[top - 1] ,p[i] )) < 0)
			top--;
		stk[top++] = p[i];
	}
	if(n > 1)
		top--;
	return top;
}


LL check(int m)
{
	//cout << m << endl;
	LL c = 2;
	LL t = 0;
	for(int i = 1; i < m; i++)
	{
		if(sign(xmult(stk[i - 1], stk[(i + 1)%(m)], stk[i])) == 0)
			c++;
		else t = (t + fpow(2, c) - (1LL + c + c * (c - 1) / 2LL) + mod) % mod, c = 2;
		//cout << c << endl;
	}
	if(c > 2)
		 t = (t + fpow(2, c) - (1LL + c + c * (c - 1) / 2LL) + mod) % mod;
	return t;
}

/////////
int main()
{

	while(~scanf("%d", &n))
	{
		for(int i = 0; i < n; i++)
		{
			double x, y;
			scanf("%lf%lf", &x, &y);
			p[i] = point(x, y);
		}
		LL ans = 0;
		LL cnt = Graham();
		//cout << cnt;
		//ans = (fpow(2, n) - check(cnt) - (1LL + n + (n - 1) * n / 2LL) + mod) % mod;
		ans = (fpow(2, n) - (1LL + n) + mod) % mod;
		for(int i = 0; i < n; i++)
		{
			map<LL, int>q;
			for(int j = i + 1; j < n; j++)
			{
				LL t;
				if(p[i].x == p[j].x)
					t = -1;
				else t = ((LL)(p[j].y - p[i].y) * fpow(p[j].x - p[i].x, mod - 2) % mod + mod ) % mod;
					q[t]++;
			}
			for(auto j : q)
			{
				ans -= fpow(2, j.se) - 1;
				ans %= mod;
			}
		}
		while(ans < 0)
			ans += mod;
		if(cnt > 2)
			printf("%lld\n", ans);
		else printf("0\n");
	}
    return 0;
}

atcoder #082 E 暴力 计算几何

原文：http://www.cnblogs.com/Yumesenya/p/7468478.html