uva 11123 - Counting Trapizoid(容斥+几何)
标签：style http color width os for
题目链接：uva 11123 - Counting Trapizoid
题目大意：给定若干个点，问有多少种梯形，不包括矩形，梯形的面积必须为正数。因为是点的集合，所以不会优重复的点。
解题思路：枚举两两点，求出该条直线，包括斜率k，偏移值c，以及长度l。已知梯形的性质，一对对边平行，也就是说一对平行但是不相等的边。
所以将所有线段按照斜率排序，假设对于某一斜率，有m条边，那么这m条边可以组成的含平行对边的四边形有C(2m),要求梯形还要减掉长度相同以及共线的情况，分别对应的是l相同和c相同，但是根据容斥原理，要加回l和c均相等的部分。
#include
#include
#include
#include
#include
using namespace std;
const int N = 205;
const double eps = 1e-9;
const double pi = 4 * atan(1.0);
struct line {
double k, c, l;
line (double k, double c = 0, double l = 0) {
this->k = k;
this->c = c;
this->l = l;
}
friend bool operator const
line& a, const line& b) {
return a.k struct state {
double c, l;
state (double c, double l) {
this->c = c;
this->l = l;
}
};
int n;
double x[N], y[N];
vector set;
vector g;
inline double distant (double xi, double yi) {
return xi * xi + yi * yi;
}
inline double cal (int a, int b) {
if (x[a] == x[b])
return x[a];
return y[a] - x[a] * ( (y[a] - y[b]) / (x[a] - x[b]) );
}
inline int C (int a) {
if (a 1)
return 0;
return a * (a - 1) / 2;
}
inline bool cmpC (const state& a, const state& b) {
if (fabs(a.c-b.c) > eps)
return a.c return a.l inline bool cmpL (const state& a, const state& b) {
return a.l int judge () {
sort(g.begin(), g.end(), cmpC);
int ans = 0, cnt = 1, tmp = 1;
/*
for (int i = 0; i
for (int i = 1; i if (fabs(g[i].c - g[i-1].c) > eps) {
ans = ans + C(cnt) - C(tmp);
cnt = 0;
tmp = 0;
}
if (fabs(g[i].l - g[i-1].l) > eps) {
ans = ans - C(tmp);
tmp = 0;
}
tmp++;
cnt++;
}
ans = ans + C(cnt) - C(tmp);
sort(g.begin(), g.end(), cmpL);
cnt = 1;
for (int i = 1; i if (fabs(g[i].l - g[i-1].l) > eps) {
ans = ans + C(cnt);
cnt = 0;
}
cnt++;
}
ans = ans + C(cnt);
return ans;
}
int solve () {
int ans = 0;
if (set.size() == 0)
return 0;
g.clear();
g.push_back(state(set[0].c, set[0].l));
for (int i = 1; i set.size(); i++) {
//printf("%d %lf!!!!!!!\n", i, set[i].k);
if (fabs(set[i].k - set[i-1].k) > eps) {
ans += C(g.size()) - judge();
g.clear();
}
g.push_back(state(set[i].c, set[i].l));
}
ans += C(g.size()) - judge();
return ans;
}
int main () {
int cas = 1;
while (scanf("%d", &n) == 1 && n) {
set.clear();
for (int i = 0; i scanf("%lf%lf", &x[i], &y[i]);
for (int j = 0; j set.push_back(line( atan2(y[j]-y[i], x[j]-x[i]), cal(i, j), distant(y[i]-y[j], x[i]-x[j]) ));
}
for (int i = 0; i set.size(); i++) {
if (set[i].k set[i].k += pi;
}
sort(set.begin(), set.end());
/*
for (int i = 0; i
printf("Case %d: %d\n", cas++, solve());
}
return 0;
}uva 11123 - Counting Trapizoid(容斥+几何),搜素材,soscw.com
uva 11123 - Counting Trapizoid(容斥+几何)
标签：style http color width os for
原文地址：http://blog.csdn.net/keshuai19940722/article/details/36015387
评论