sum con gmail mail name 线上 pre 斜率
给出点集,然后求一个凸包的所有的子凸包的贡献总和,贡献计算是凸包内部含边界上点的数量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 ([email protected])
- * @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.bubuko.com/infodetail-2289258.html