2010 ACM 赛前笔记
2010.10.11
要为出发做准备了，今天和Ultramanhu和Answeror一起去买了火车票，真是搞笑了，提前六天去买票，竟然动车没坐票了，难道世博就这么猛？只有买周四晚上出发的非动车卧铺票了。顺便带个三国杀什么的去玩，不过估计去的时候也没什么心思玩，等回来的时候再用吧。
回来的时候Answeror推荐我们去吃大娘水饺，然后就去了，我买了半斤水饺，花了25.5块，这么贵，果然学校外面就是贵啊，不过挺好吃的。起码比学校里的好太多了，而且那个水饺很有分量。
今晚协议到线段树的题竟然效率和不用线段树的一样，气死我了，明天看看别人怎么写的，然后改，顺便看看二维线段树，再顺便复习一下树状数组。
2010.10.12
本来打算好好看线段树的，结果线段树的基本操作是会了，可是还是不熟，这个很麻烦啊。今天一定要吧线段树搞定，明天整理一些以前写过的东西车上看看。
好吧，今天我们去买回程票（防止买不到坐票），结果售票员告诉我们明天才能买，原来我们说的提前六天是(12, 18],官方的是[12,18)。这个郁闷了，不过售票员的态度让我很不爽。
今天优化了昨天的线段树代码，发现用sort然后去重点的离散化竟然效率是用map离散化的10倍左右，太夸张了。
今天让同学帮忙交请假条来着，结果上课一半时间了他告诉我我们不是同一个老师，郁闷。更郁闷的是他们老师很猛，每节课都点名，而且点一个出去一个的那种点名，下课还特别晚，等他出来，我那个上课的老师早就下课走人了。等我赶到教室的时候灯都黑了，结果请假条没交成，只能下次上课去交了，真是麻烦。
今天等那个倒霉孩子的时候看到了一个帖子，有人遇见晓了，帖子地址：http://bbs.unistar.cn/dispbbs.asp?boardid=209&Id=58429
今天再把二维线段树看下就结束吧，明天看RMQ的ST算法，然后整理材料。
2010.10.14
昨天只是复习了一下算法，没看什么新东西，顺便把模板打印了，模板的厚度还可以接受，我的和Ultrahanhu的加起来110多页，上午还去南站买了票，结果前天没到时间还不能卖，昨天上午所有回来的动车坐票都卖完了，特快还没卧铺，只好买了硬座了，想想14个小时的硬座，好吧会坐到PP疼的。
今天上午收到天津同学的短信，说周六大降温，为了以防万一，我就多带点衣服过去了，两件衣服一条裤子，好像有点多了。很期待Ultramanhu会带多少东西去，不要带个旅行箱就好，等会带队老师来请客吃饭，不错哈，我早餐都没吃。
我把我所有的手机电池都带上了，路上听歌，顺便看看北方的WCDMA怎么样。
按照计划我们是明天中午到，然后去报到，然后去宾馆，然后去买天津到北京的车票，然后吃晚饭，然后没有然后了。
今天中午和杨老师一起去吃饭了，按他的说法，下午3:30就要去南站了，看来我们需要等火车等2个多小时啦。
今天下午就出发了，祝愿我们有个好成绩吧。
线段树相关问题 (引用 PKU POJ题目) 整理
1.RangeMinimum、Maximum Query问题（计算单调区间内出现最多（少）的次数）
对元素的起点做离散化，再把离散化后的位置作为线段树的[l, r),记录次数为t.
对输入区间a, b:
POJ PKU 1474 Video Surveillance 解题报告
题目链接：http://poj.org/problem?id=1474
写这题的目的是看完了zzy的论文，写了半平面交，验证一下正确性，结果发现我写的问题还是很多的。
题目大意是问能不能放一个摄像机，使得摄像机能看到整个多边形内部。
ACM 计算几何 个人模板
/**
* 二维ACM计算几何模板
* 注意变量类型更改和EPS
* #include <cmath>
* #include <cstdio>
* By OWenT
*/
const double eps = 1e-8;
const double pi = std::acos(-1.0);
//点
class point
{
public:
double x, y;
point(){};
point(double x, double y):x(x),y(y){};
static int xmult(const point &ps, const point &pe, const point &po)
{
return (ps.x - po.x) * (pe.y - po.y) - (pe.x - po.x) * (ps.y - po.y);
}
//相对原点的差乘结果，参数：点[_Off]
//即由原点和这两个点组成的平行四边形面积
double operator *(const point &_Off) const
{
return x * _Off.y - y * _Off.x;
}
//相对偏移
point operator - (const point &_Off) const
{
return point(x - _Off.x, y - _Off.y);
}
//点位置相同(double类型)
bool operator == (const point &_Off) const
{
return std::fabs(_Off.x - x) < eps && std::fabs(_Off.y - y) < eps;
}
//点位置不同(double类型)
bool operator != (const point &_Off) const
{
return ((*this) == _Off) == false;
}
//两点间距离的平方
double dis2(const point &_Off) const
{
return (x - _Off.x) * (x - _Off.x) + (y - _Off.y) * (y - _Off.y);
}
//两点间距离
double dis(const point &_Off) const
{
return std::sqrt((x - _Off.x) * (x - _Off.x) + (y - _Off.y) * (y - _Off.y));
}
};
//两点表示的向量
class pVector
{
public:
point s, e;//两点表示，起点[s]，终点[e]
double a, b, c;//一般式,ax+by+c=0
pVector(){}
pVector(const point &s, const point &e):s(s),e(e){}
//向量与点的叉乘,参数：点[_Off]
//[点相对向量位置判断]
double operator *(const point &_Off) const
{
return (_Off.y - s.y) * (e.x - s.x) - (_Off.x - s.x) * (e.y - s.y);
}
//向量与向量的叉乘,参数：向量[_Off]
double operator *(const pVector &_Off) const
{
return (e.x - s.x) * (_Off.e.y - _Off.s.y) - (e.y - s.y) * (_Off.e.x - _Off.s.x);
}
//从两点表示转换为一般表示
bool pton()
{
a = s.y - e.y;
b = e.x - s.x;
c = s.x * e.y - s.y * e.x;
return true;
}
//-----------点和直线（向量）-----------
//点在向量左边（右边的小于号改成大于号即可,在对应直线上则加上=号）
//参数：点[_Off],向量[_Ori]
friend bool operator<(const point &_Off, const pVector &_Ori)
{
return (_Ori.e.y - _Ori.s.y) * (_Off.x - _Ori.s.x)
< (_Off.y - _Ori.s.y) * (_Ori.e.x - _Ori.s.x);
}
//点在直线上,参数：点[_Off]
bool lhas(const point &_Off) const
{
return std::fabs((*this) * _Off) < eps;
}
//点在线段上,参数：点[_Off]
bool shas(const point &_Off) const
{
return lhas(_Off)
&& _Off.x - std::min(s.x, e.x) > -eps && _Off.x - std::max(s.x, e.x) < eps
&& _Off.y - std::min(s.y, e.y) > -eps && _Off.y - std::max(s.y, e.y) < eps;
}
//点到直线/线段的距离
//参数： 点[_Off], 是否是线段[isSegment](默认为直线)
double dis(const point &_Off, bool isSegment = false)
{
//化为一般式
pton();
//到直线垂足的距离
double td = (a * _Off.x + b * _Off.y + c) / sqrt(a * a + b * b);
//如果是线段判断垂足
if(isSegment)
{
double xp = (b * b * _Off.x - a * b * _Off.y - a * c) / ( a * a + b * b);
double yp = (-a * b * _Off.x + a * a * _Off.y - b * c) / (a * a + b * b);
double xb = std::max(s.x, e.x);
double yb = std::max(s.y, e.y);
double xs = s.x + e.x - xb;
double ys = s.y + e.y - yb;
if(xp > xb + eps || xp < xs - eps || yp > yb + eps || yp < ys - eps)
td = std::min(_Off.dis(s), _Off.dis(e));
}
return fabs(td);
}
//关于直线对称的点
point mirror(const point &_Off) const
{
//注意先转为一般式
point ret;
double d = a * a + b * b;
ret.x = (b * b * _Off.x - a * a * _Off.x - 2 * a * b * _Off.y - 2 * a * c) / d;
ret.y = (a * a * _Off.y - b * b * _Off.y - 2 * a * b * _Off.x - 2 * b * c) / d;
return ret;
}
//计算两点的中垂线
static pVector ppline(const point &_a, const point &_b)
{
pVector ret;
ret.s.x = (_a.x + _b.x) / 2;
ret.s.y = (_a.y + _b.y) / 2;
//一般式
ret.a = _b.x - _a.x;
ret.b = _b.y - _a.y;
ret.c = (_a.y - _b.y) * ret.s.y + (_a.x - _b.x) * ret.s.x;
//两点式
if(std::fabs(ret.a) > eps)
{
ret.e.y = 0.0;
ret.e.x = - ret.c / ret.a;
if(ret.e == ret. s)
{
ret.e.y = 1e10;
ret.e.x = - (ret.c - ret.b * ret.e.y) / ret.a;
}
}
else
{
ret.e.x = 0.0;
ret.e.y = - ret.c / ret.b;
if(ret.e == ret. s)
{
ret.e.x = 1e10;
ret.e.y = - (ret.c - ret.a * ret.e.x) / ret.b;
}
}
return ret;
}
//------------直线和直线（向量）-------------
//直线重合,参数：直线向量[_Off]
bool equal(const pVector &_Off) const
{
return lhas(_Off.e) && lhas(_Off.s);
}
//直线平行，参数：直线向量[_Off]
bool parallel(const pVector &_Off) const
{
return std::fabs((*this) * _Off) < eps;
}
//两直线交点，参数：目标直线[_Off]
point crossLPt(pVector _Off)
{
//注意先判断平行和重合
point ret = s;
double t = ((s.x - _Off.s.x) * (_Off.s.y - _Off.e.y) - (s.y - _Off.s.y) * (_Off.s.x - _Off.e.x))
/ ((s.x - e.x) * (_Off.s.y - _Off.e.y) - (s.y - e.y) * (_Off.s.x - _Off.e.x));
ret.x += (e.x - s.x) * t;
ret.y += (e.y - s.y) * t;
return ret;
}
//------------线段和直线（向量）----------
//线段和直线交
//参数：线段[_Off]
bool crossSL(const pVector &_Off) const
{
double rs = (*this) * _Off.s;
double re = (*this) * _Off.e;
return rs * re < eps;
}
//------------线段和线段（向量）----------
//判断线段是否相交(注意添加eps)，参数：线段[_Off]
bool isCrossSS(const pVector &_Off) const
{
//1.快速排斥试验判断以两条线段为对角线的两个矩形是否相交
//2.跨立试验（等于0时端点重合）
return (
(std::max(s.x, e.x) >= std::min(_Off.s.x, _Off.e.x)) &&
(std::max(_Off.s.x, _Off.e.x) >= std::min(s.x, e.x)) &&
(std::max(s.y, e.y) >= std::min(_Off.s.y, _Off.e.y)) &&
(std::max(_Off.s.y, _Off.e.y) >= std::min(s.y, e.y)) &&
((pVector(_Off.s, s) * _Off) * (_Off * pVector(_Off.s, e)) >= 0.0) &&
((pVector(s, _Off.s) * (*this)) * ((*this) * pVector(s, _Off.e)) >= 0.0)
);
}
};
class polygon
{
public:
const static long maxpn = 100;
point pt[maxpn];//点（顺时针或逆时针）
long n;//点的个数
point& operator[](int _p)
{
return pt[_p];
}
//求多边形面积，多边形内点必须顺时针或逆时针
double area() const
{
double ans = 0.0;
int i;
for(i = 0; i < n; i ++)
{
int nt = (i + 1) % n;
ans += pt[i].x * pt[nt].y - pt[nt].x * pt[i].y;
}
return std::fabs(ans / 2.0);
}
//求多边形重心，多边形内点必须顺时针或逆时针
point gravity() const
{
point ans;
ans.x = ans.y = 0.0;
int i;
double area = 0.0;
for(i = 0; i < n; i ++)
{
int nt = (i + 1) % n;
double tp = pt[i].x * pt[nt].y - pt[nt].x * pt[i].y;
area += tp;
ans.x += tp * (pt[i].x + pt[nt].x);
ans.y += tp * (pt[i].y + pt[nt].y);
}
ans.x /= 3 * area;
ans.y /= 3 * area;
return ans;
}
//判断点在凸多边形内，参数：点[_Off]
bool chas(const point &_Off) const
{
double tp = 0, np;
int i;
for(i = 0; i < n; i ++)
{
np = pVector(pt[i], pt[(i + 1) % n]) * _Off;
if(tp * np < -eps)
return false;
tp = (std::fabs(np) > eps)?np: tp;
}
return true;
}
//判断点是否在任意多边形内[射线法]，O(n)
bool ahas(const point &_Off) const
{
int ret = 0;
double infv = 1e-10;//坐标系最大范围
pVector l = pVector(_Off, point( -infv ,_Off.y));
for(int i = 0; i < n; i ++)
{
pVector ln = pVector(pt[i], pt[(i + 1) % n]);
if(fabs(ln.s.y - ln.e.y) > eps)
{
point tp = (ln.s.y > ln.e.y)? ln.s: ln.e;
if(fabs(tp.y - _Off.y) < eps && tp.x < _Off.x + eps)
ret ++;
}
else if(ln.isCrossSS(l))
ret ++;
}
return (ret % 2 == 1);
}
//凸多边形被直线分割,参数：直线[_Off]
polygon split(pVector _Off)
{
//注意确保多边形能被分割
polygon ret;
point spt[2];
double tp = 0.0, np;
bool flag = true;
int i, pn = 0, spn = 0;
for(i = 0; i < n; i ++)
{
if(flag)
pt[pn ++] = pt[i];
else
ret.pt[ret.n ++] = pt[i];
np = _Off * pt[(i + 1) % n];
if(tp * np < -eps)
{
flag = !flag;
spt[spn ++] = _Off.crossLPt(pVector(pt[i], pt[(i + 1) % n]));
}
tp = (std::fabs(np) > eps)?np: tp;
}
ret.pt[ret.n ++] = spt[0];
ret.pt[ret.n ++] = spt[1];
n = pn;
return ret;
}
//-------------凸包-------------
//Graham扫描法，复杂度O(nlg(n)),结果为逆时针
//#include <algorithm>
static bool graham_cmp(const point &l, const point &r)//凸包排序函数
{
return l.y < r.y || (l.y == r.y && l.x < r.x);
}
polygon& graham(point _p[], int _n)
{
int i, len;
std::sort(_p, _p + _n, polygon::graham_cmp);
n = 1;
pt[0] = _p[0], pt[1] = _p[1];
for(i = 2; i < _n; i ++)
{
while(n && point::xmult(_p[i], pt[n], pt[n - 1]) >= 0)
n --;
pt[++ n] = _p[i];
}
len = n;
pt[++ n] = _p[_n - 2];
for(i = _n - 3; i >= 0; i --)
{
while(n != len && point::xmult(_p[i], pt[n], pt[n - 1]) >= 0)
n --;
pt[++ n] = _p[i];
}
return (*this);
}
//凸包旋转卡壳(注意点必须顺时针或逆时针排列)
//返回值凸包直径的平方（最远两点距离的平方）
double rotating_calipers()
{
int i = 1;
double ret = 0.0;
pt[n] = pt[0];
for(int j = 0; j < n; j ++)
{
while(fabs(point::xmult(pt[j], pt[j + 1], pt[i + 1])) > fabs(point::xmult(pt[j], pt[j + 1], pt[i])) + eps)
i = (i + 1) % n;
//pt[i]和pt[j],pt[i + 1]和pt[j + 1]可能是对踵点
ret = std::max(ret, std::max(pt[i].dis(pt[j]), pt[i + 1].dis(pt[j + 1])));
}
return ret;
}
//凸包旋转卡壳(注意点必须逆时针排列)
//返回值两凸包的最短距离
double rotating_calipers(polygon &_Off)
{
int i = 0;
double ret = 1e10;//inf
pt[n] = pt[0];
_Off.pt[_Off.n] = _Off.pt[0];
//注意凸包必须逆时针排列且pt[0]是左下角点的位置
while(_Off.pt[i + 1].y > _Off.pt[i].y)
i = (i + 1) % _Off.n;
for(int j = 0; j < n; j ++)
{
double tp;
//逆时针时为 >,顺时针则相反
while((tp = point::xmult(pt[j], pt[j + 1], _Off.pt[i + 1]) - point::xmult( pt[j], pt[j + 1], _Off.pt[i])) > eps)
i = (i + 1) % _Off.n;
//(pt[i],pt[i+1])和(_Off.pt[j],_Off.pt[j + 1])可能是最近线段
ret = std::min(ret, pVector(pt[j], pt[j + 1]).dis(_Off.pt[i], true));
ret = std::min(ret, pVector(_Off.pt[i], _Off.pt[i + 1]).dis(pt[j + 1], true));
if(tp > -eps)//如果不考虑TLE问题最好不要加这个判断
{
ret = std::min(ret, pVector(pt[j], pt[j + 1]).dis(_Off.pt[i + 1], true));
ret = std::min(ret, pVector(_Off.pt[i], _Off.pt[i + 1]).dis(pt[j], true));
}
}
return ret;
}
//-----------半平面交-------------
//复杂度:O(nlog2(n))
//#include <algorithm>
//半平面计算极角函数[如果考虑效率可以用成员变量记录]
static double hpc_pa(const pVector &_Off)
{
return atan2(_Off.e.y - _Off.s.y, _Off.e.x - _Off.s.x);
}
//半平面交排序函数[优先顺序: 1.极角 2.前面的直线在后面的左边]
static bool hpc_cmp(const pVector &l, const pVector &r)
{
double lp = hpc_pa(l), rp = hpc_pa(r);
if(fabs(lp - rp) > eps)
return lp < rp;
return point::xmult(l.s, r.e, r.s) < 0.0;
}
//用于计算的双端队列
pVector dequeue[maxpn];
//获取半平面交的多边形（多边形的核）
//参数：向量集合[l]，向量数量[ln];(半平面方向在向量左边）
//函数运行后如果n[即返回多边形的点数量]为0则不存在半平面交的多边形（不存在区域或区域面积无穷大）
polygon& halfPanelCross(pVector _Off[], int ln)
{
int i, tn;
n = 0;
std::sort(_Off, _Off + ln, hpc_cmp);
//平面在向量左边的筛选
for(i = tn = 1; i < ln; i ++)
if(fabs(hpc_pa(_Off[i]) - hpc_pa(_Off[i - 1])) > eps)
_Off[tn ++] = _Off[i];
ln = tn;
int bot = 0, top = 1;
dequeue[0] = _Off[0];
dequeue[1] = _Off[1];
for(i = 2; i < ln; i ++)
{
if(dequeue[top].parallel(dequeue[top - 1]) ||
dequeue[bot].parallel(dequeue[bot + 1]))
return (*this);
while(bot < top &&
point::xmult(dequeue[top].crossLPt(dequeue[top - 1]), _Off[i].e, _Off[i].s) > eps)
top --;
while(bot < top &&
point::xmult(dequeue[bot].crossLPt(dequeue[bot + 1]), _Off[i].e, _Off[i].s) > eps)
bot ++;
dequeue[++ top] = _Off[i];
}
while(bot < top &&
point::xmult(dequeue[top].crossLPt(dequeue[top - 1]), dequeue[bot].e, dequeue[bot].s) > eps)
top --;
while(bot < top &&
point::xmult(dequeue[bot].crossLPt(dequeue[bot + 1]), dequeue[top].e, dequeue[top].s) > eps)
bot ++;
//计算交点(注意不同直线形成的交点可能重合)
if(top <= bot + 1)
return (*this);
for(i = bot; i < top; i ++)
pt[n ++] = dequeue[i].crossLPt(dequeue[i + 1]);
if(bot < top + 1)
pt[n ++] = dequeue[bot].crossLPt(dequeue[top]);
return (*this);
}
};
class circle
{
public:
point c;//圆心
double r;//半径
double db, de;//圆弧度数起点， 圆弧度数终点(逆时针0-360)
//-------圆---------
//判断圆在多边形内
bool inside(const polygon &_Off) const
{
if(_Off.ahas(c) == false)
return false;
for(int i = 0; i < _Off.n; i ++)
{
pVector l = pVector(_Off.pt[i], _Off.pt[(i + 1) % _Off.n]);
if(l.dis(c, true) < r - eps)
return false;
}
return true;
}
//判断多边形在圆内（线段和折线类似）
bool has(const polygon &_Off) const
{
for(int i = 0; i < _Off.n; i ++)
if(_Off.pt[i].dis2(c) > r * r - eps)
return false;
return true;
}
//-------圆弧-------
//圆被其他圆截得的圆弧，参数：圆[_Off]
circle operator-(circle &_Off) const
{
//注意圆必须相交，圆心不能重合
double d2 = c.dis2(_Off.c);
double d = c.dis(_Off.c);
double ans = std::acos((d2 + r * r - _Off.r * _Off.r) / (2 * d * r));
point py = _Off.c - c;
double oans = std::atan2(py.y, py.x);
circle res;
res.c = c;
res.r = r;
res.db = oans + ans;
res.de = oans - ans + 2 * pi;
return res;
}
//圆被其他圆截得的圆弧，参数：圆[_Off]
circle operator+(circle &_Off) const
{
//注意圆必须相交，圆心不能重合
double d2 = c.dis2(_Off.c);
double d = c.dis(_Off.c);
double ans = std::acos((d2 + r * r - _Off.r * _Off.r) / (2 * d * r));
point py = _Off.c - c;
double oans = std::atan2(py.y, py.x);
circle res;
res.c = c;
res.r = r;
res.db = oans - ans;
res.de = oans + ans;
return res;
}
//过圆外一点的两条切线
//参数：点[_Off](必须在圆外),返回：两条切线(切线的s点为_Off,e点为切点)
std::pair<pVector, pVector> tangent(const point &_Off) const
{
double d = c.dis(_Off);
//计算角度偏移的方式
double angp = std::acos(r / d), ango = std::atan2(_Off.y - c.y, _Off.x - c.x);
point pl = point(c.x + r * std::cos(ango + angp), c.y + r * std::sin(ango + angp)),
pr = point(c.x + r * std::cos(ango - angp), c.y + r * std::sin(ango - angp));
return std::make_pair(pVector(_Off, pl), pVector(_Off, pr));
}
//计算直线和圆的两个交点
//参数：直线[_Off](两点式)，返回两个交点，注意直线必须和圆有两个交点
std::pair<point, point> cross(pVector _Off) const
{
_Off.pton();
//到直线垂足的距离
double td = fabs(_Off.a * c.x + _Off.b * c.y + _Off.c) / sqrt(_Off.a * _Off.a + _Off.b * _Off.b);
//计算垂足坐标
double xp = (_Off.b * _Off.b * c.x - _Off.a * _Off.b * c.y - _Off.a * _Off.c) / ( _Off.a * _Off.a + _Off.b * _Off.b);
double yp = (- _Off.a * _Off.b * c.x + _Off.a * _Off.a * c.y - _Off.b * _Off.c) / (_Off.a * _Off.a + _Off.b * _Off.b);
double ango = std::atan2(yp - c.y, xp - c.x);
double angp = std::acos(td / r);
return std::make_pair(point(c.x + r * std::cos(ango + angp), c.y + r * std::sin(ango + angp)),
point(c.x + r * std::cos(ango - angp), c.y + r * std::sin(ango - angp)));
}
};
class triangle
{
public:
point a, b, c;//顶点
triangle(){}
triangle(point a, point b, point c): a(a), b(b), c(c){}
//计算三角形面积
double area()
{
return fabs(point::xmult(a, b, c)) / 2.0;
}
//计算三角形外心
//返回：外接圆圆心
point circumcenter()
{
pVector u,v;
u.s.x = (a.x + b.x) / 2;
u.s.y = (a.y + b.y) / 2;
u.e.x = u.s.x - a.y + b.y;
u.e.y = u.s.y + a.x - b.x;
v.s.x = (a.x + c.x) / 2;
v.s.y = (a.y + c.y) / 2;
v.e.x = v.s.x - a.y + c.y;
v.e.y = v.s.y + a.x - c.x;
return u.crossLPt(v);
}
//计算三角形内心
//返回：内接圆圆心
point incenter()
{
pVector u, v;
double m, n;
u.s = a;
m = atan2(b.y - a.y, b.x - a.x);
n = atan2(c.y - a.y, c.x - a.x);
u.e.x = u.s.x + cos((m + n) / 2);
u.e.y = u.s.y + sin((m + n) / 2);
v.s = b;
m = atan2(a.y - b.y, a.x - b.x);
n = atan2(c.y - b.y, c.x - b.x);
v.e.x = v.s.x + cos((m + n) / 2);
v.e.y = v.s.y + sin((m + n) / 2);
return u.crossLPt(v);
}
//计算三角形垂心
//返回：高的交点
point perpencenter()
{
pVector u,v;
u.s = c;
u.e.x = u.s.x - a.y + b.y;
u.e.y = u.s.y + a.x - b.x;
v.s = b;
v.e.x = v.s.x - a.y + c.y;
v.e.y = v.s.y + a.x - c.x;
return u.crossLPt(v);
}
//计算三角形重心
//返回：重心
//到三角形三顶点距离的平方和最小的点
//三角形内到三边距离之积最大的点
point barycenter()
{
pVector u,v;
u.s.x = (a.x + b.x) / 2;
u.s.y = (a.y + b.y) / 2;
u.e = c;
v.s.x = (a.x + c.x) / 2;
v.s.y = (a.y + c.y) / 2;
v.e = b;
return u.crossLPt(v);
}
//计算三角形费马点
//返回：到三角形三顶点距离之和最小的点
point fermentpoint()
{
point u, v;
double step = fabs(a.x) + fabs(a.y) + fabs(b.x) + fabs(b.y) + fabs(c.x) + fabs(c.y);
int i, j, k;
u.x = (a.x + b.x + c.x) / 3;
u.y = (a.y + b.y + c.y) / 3;
while (step > eps)
{
for (k = 0; k < 10; step /= 2, k ++)
{
for (i = -1; i <= 1; i ++)
{
for (j =- 1; j <= 1; j ++)
{
v.x = u.x + step * i;
v.y = u.y + step * j;
if (u.dis(a) + u.dis(b) + u.dis(c) > v.dis(a) + v.dis(b) + v.dis(c))
u = v;
}
}
}
}
return u;
}
};
The 35th ACM/ICPC Asia Regional Tianjin Site —— Online Contest 1009 Convex 解题报告
The 35th ACM/ICPC Asia Regional Tianjin Site —— Online Contest
2010年天津赛 网络赛 I题 Convex
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3629
题目大意是给你700个点，问从中选4个点组成凸四边形的方法数
比赛的时候其实最终得到了正确的方法，结果因为写搓了导致TLE，HDU的64位整形必须用I64d，导致WA
简易四则运算(ACM个人模板)
/**
* 简易四则运算（栈实现）
* #include <stack>
* #include <cstring>
*/
std::stack<char> opr;
std::stack<double> num;
char oprPRI[256];
//初始化调用
void initCalc()
{
//优先级设置
char oprMap[7][2] = { {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'^', 3}, {'(', 100}, {')', 0} };
for(int i = 0; i < 7; i ++)
oprPRI[oprMap[i][0]] = oprMap[i][1];
}
bool checkNum(char c)
{
return c == '.' || (c >= '0' && c <= '9');
}
double calcOpr(double l, double r, char opr)
{
switch(opr)
{
case '+': return l + r;
case '-': return l - r;
case '*': return l * r;
case '/': return l / r;
case '^': return ::pow(l, r);
}
return 0.0;
}
void calcStack()
{
double cl, cr;
cr = num.top();
num.pop();
cl = num.top();
num.pop();
num.push(::calcOpr(cl, cr, opr.top()));
opr.pop();
}
double calc(const char str[])
{
while(!opr.empty())
opr.pop();
while(!num.empty())
num.pop();
int i = 0, len = strlen(str);
num.push(0.0);
opr.push('(');
while(i < len)
{
if(::checkNum(str[i]))
{
double l;
::sscanf(str + i, "%lf", &l);
while(::checkNum(str[i]))
i ++;
num.push(l);
}
else
{
char c = str[i ++];
if(c == ')')
{
while(opr.top() != '(')
calcStack();
opr.pop();
}
else if(oprPRI[c] > oprPRI[opr.top()])
opr.push(c);
else
{
while(opr.top() != '(' && oprPRI[c] <= oprPRI[opr.top()])
calcStack();
opr.push(c);
}
}
}
while(opr.size() > 1)
calcStack();
return num.top();
}
数论模板（个人模板）
基础函数:
// 最大公约数,欧几里得定理
int gcd(int a, int b)
{
return b?gcd(b, a % b): a;
}
// 拓展欧几里得定理
// 求解ax + by = gcd(a,b)
int ext_gcd(int a, int b, int &x, int &y)
{
int tmp, ret;
if(!b)
{
x = 1;
y = 0;
return a;
}
ret = ext_gcd(b, a % b, x, y);
tmp = x;
x = y;
y = tmp - (a / b) * y;
return ret;
}
//交换数值
void swap(int &a, int &b)
{
a ^= b ^= a ^= b;
}
/**
* a的b次方Mod c
* 参数为整数
* 使用时注意修改类型
*/
int PowerMod(int a, int b, int c)
{
int tp = 1;
while (b)
{
if (b & 1)
tp = (tp * a) % c;
a = (a * a) % c;
b >>= 1;
}
return tp;
}
1.欧拉函数
Ψ（n） = 小于n且与n互质的数的个数
POJ PKU 2826 An Easy Problem?! 解题报告
题目链接： http://acm.pku.edu.cn/JudgeOnline/problem?id=2826
大致意思是给你两条线段，问组成的开口向上的V形区域能盛多少雨水。雨水是垂直落下的。
显然线段不相交，或者平行，重合，或者有一条斜率为0时结果为0.00
关于差分约束（转载）
关于差分约束（转载）
（本文假设读者已经有以下知识：最短路径的基本性质、Bellman-Ford算法。） 比如有这样一组不等式：
$$ \begin{cases} X1 - X2 <= 0 \\ X1 - X5 <= (-1) \\ X2 - X5 <= 1 \\ X3 - X1 <= 5 \\ X4 - X1 <= 4 \\ X4 - X3 <= (-1) \\ X5 - X3 <= (-3) \\ X5 - X4 <= (-3) \end{cases} $$(1)
计算几何算法概览[转载]
一、引言
计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到帮助。
POJ PKU 1986 Distance Queries 解题报告
题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=1986
这是一道并查集+树的题，采用Tarjan离线算法
首先BS一下出题的人，也太懒了吧，还要我们看1984题才知道输入
题目的意思是告诉一个节点数为40000的树，问我们两个节点间的距离。实际上就是找出公共父节点，Tarjan算法写挫了很容易TLE，我开始用Vector就写搓了，结果TLE，后来重写，自己写邻接表然后AC了。
POJ PKU 2446 Chessboard 解题报告
题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=2446
这是一道匹配题，把行数（r）和列数（c）按（r+c）%2分成两组，然后连边，做一次二分图匹配，可以直接用匈牙利算法
匹配数等于两组的元素个数则为YES，否则NO
C#格式化输出(记录)
int a = 12345678;
//格式为sring输出
Label1.Text = string.Format("asdfadsf{0}adsfasdf",a);
Label2.Text = "asdfadsf"+a.ToString()+"adsfasdf";
Label1.Text = string.Format("asdfadsf{0:C}adsfasdf",a);//asdfadsf￥1,234.00adsfasdf
Label2.Text = "asdfadsf"+a.ToString("C")+"adsfasdf";//asdfadsf￥1,234.00adsfasdf
double b = 1234.12543;
int a = 12345678;
//格式为特殊的string样式输出
Label1.Text = string.Format("asdfadsf{0:C}adsfasdf",b);//asdfadsf￥1,234.13adsfasdf
Label2.Text = "asdfadsf"+b.ToString("C")+"adsfasdf";//asdfadsf￥1,234.13adsfasdf
Label1.Text = string.Format("{0:C3}",b);//￥1,234.125
Label2.Text = b.ToString("C3");//￥1,234.125
Label1.Text = string.Format("{0:d}",a);//十进制--12345678
Label2.Text = b.ToString("d");//十进制--相同的类型，转换报错
Label1.Text = string.Format("{0:e}",a);//指数--1.234568e+007
Label2.Text = b.ToString("e");//指数--1.234125e+003
Label1.Text = string.Format("{0:f}",a);//定点数--12345678.00
Label2.Text = b.ToString("f");//定点数--1234.13
Label1.Text = string.Format("{0:n}",a);//数值--12,345,678.00
Label2.Text = b.ToString("n");//数值--1,234.13
Label1.Text = string.Format("{0:x}",a);//十六进制--bc614e
Label2.Text = b.ToString("x");//16--带有小数不能转换，出错
Label1.Text = string.Format("{0:g}",a);//通用为最紧凑--12345678
Label2.Text = b.ToString("g");//通用为最紧凑--1234.12543
Label1.Text = string.Format("{0:r}",a);//转来转去不损失精度--整数不允许用，报错
Label2.Text = b.ToString("r");//转来转去不损失精度--1234.12543
double b = 4321.12543;
int a = 1234;
自定义模式输出：
//"0"描述：占位符，如果可能，填充位
Label1.Text = string.Format("{0:000000}",a);// 001234
Label2.Text = string.Format("{0:000000}",b);// 004321
//"#"描述：占位符，如果可能，填充位
Label1.Text = string.Format("{0:####### }",a);// 1234
Label2.Text = string.Format("{0:####### }",b);// 4321
Label1.Text = string.Format("{0:#0#### }",a);// 01234
Label2.Text = string.Format("{0:0#0000}",b);// 004321
//"."描述：小数点
Label1.Text = string.Format("{0:000.000}",a);//1234.000
Label2.Text = string.Format("{0:000.000}",b);//4321.125
double b = 87654321.12543;
int a = 12345678;
//","描述：数字分组，也用于增倍器
Label1.Text = string.Format("{0:0,00}",a);// 12,345,678
Label2.Text = string.Format("{0:0,00}",b);// 87,654,32
Label1.Text = string.Format("{0:0,}",a);// 12346
Label2.Text = string.Format("{0:0,}",b);// 87654
Label1.Text = string.Format("{0:0,,}",a);// 12
Label2.Text = string.Format("{0:0,,}",b);// 88
Label1.Text = string.Format("{0:0,,,}",a);// 0
Label2.Text = string.Format("{0:0,,,}",b);// 0
//"%"描述：格式为百分数
Label1.Text = string.Format("{ 0:0% }",a);// 1234567800%
Label2.Text = string.Format("{ 0:#% }",b);// 8765432113%
Label1.Text = string.Format("{ 0:0.00% }",a);// 1234567800.00%
Label2.Text = string.Format("{ 0:#.00% }",b);// 8765432112.54%
//"abc"描述：显示单引号内的文本
Label1.Text = string.Format("{0:'文本'0}",a);// 文本12345678
Label2.Text = string.Format("{0:文本0}",b);// 文本87654321
//"\"描述：后跟1要打印字的字符，也用于转移符\n等
Label1.Text = string.Format("\"你好！\"");// "你好！"
Label2.Text = string.Format("[url=file://\\c\\books\\new\\we.asp]\\c\\books\\new\\we.asp");//\c\books\new\we.asp
//"@"描述：后跟要打印字的字符,
Label1.Text = string.Format(@"""你好！"""); // "你好！"要打印"则需要输入两对才可以
Label2.Text = string.Format(@"\c\books\new\we.asp");//\c\books\new\we.asp
USACO 2008 March Gold Cow Jogging 解题报告
题目链接：http://202.120.106.94/onlinejudge/problemshow.php?pro_id=143
这道题嘛，怎么说呢，好吧中等题
要求算出下山的前k短路的路长度
由于一定是下山所以可以用邻接表记录路径，然后用一个优先队列记录已有的到n的路长度
POJ PKU 3659 Cell Phone Network 解题报告
题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=3659
这题不算难题了，基本算是中等题
题目大意是给出一颗树，在一些点建一个信号塔，信号塔覆盖范围是其所在点和邻近点，问最少几个信号塔可以覆盖全区域
浙江理工 省赛总结 team62 By OWenT of Coeus
这次比赛成绩比预期差
开始Ultramanhu调整IDE
Q Boy从头开始看题
我的任务是倒数看题，最后看的题目是J，I，H，G
我看完J觉得J可做（哈密顿回路），但是需要很长时间。就首先放着继续看题
树状数组模块(个人模板)
树状数组模块
ACM个人模板
POJ 2155 题目测试通过
/**
* 树状数组模块
* 下标从0开始
*/
typedef long DG_Ran;
typedef long DG_Num;
const DG_Num DG_MAXN = 1005;
//2^n
DG_Num LowBit(DG_Num n)
{
return n & (-n);
}
//获取父节点索引
DG_Num DGFather(DG_Num n)
{
return n + LowBit(n + 1);
}
//获取小的兄弟节点索引
DG_Num DGBrother(DG_Num n)
{
return n - LowBit(n + 1);
}
//查找增加树状数组前pos项和
//参数(树状数组[in],索引[in],初始赋0即查找前n项和[out])
//复杂度:log(n)
void DGFind(DG_Ran *g,DG_Num pos,DG_Ran &sum)
{
sum += *(g + pos);
if(pos >= LowBit(pos + 1))
DGFind(g, pos - LowBit(pos + 1), sum);
}
//查找对应线性数组元素
//参数(树状数组[in],索引[in]).
//返回值:对应线性数组元素log(n)
//复杂度:log(n)
DG_Ran DGFindEle(DG_Ran *g,DG_Num pos)
{
DG_Ran a = 0 , b = 0;
DGFind(g, pos, a);
if(pos)
{
DGFind(g,pos - 1,b);
return a - b;
}
else
return a;
}
//树状数组,增加节点
//参数:树状数组[out],原数组大小[in],新增线性数组值[in]
//复杂度:log(n)
DG_Ran DGAdd(DG_Ran *g,DG_Num n,DG_Ran val)
{
*(g + n) = val;
DG_Num a = n;
DG_Num b = 1;
while((a & (~b)) != a)
{
*(g + n) += *(g + a - 1);
a &= (~b);
b <<= 1;
}
return n + 1;
}
//构建树状数组
//参数:线性数组[in],数组大小[in],树状数组[out]
//复杂度:nlog(n)
DG_Ran DGCreate(DG_Ran *g,DG_Num n,DG_Ran *tg)
{
DG_Num i;
*tg = *g;
for(i = 1 ; i < n ; i ++)
DGAdd(tg,i,*(g + i));
return n;
}
//修改指定位置值
//参数:线性数组[in],数组位置[in],数组大小[in],新值[in]
//复杂度:log(n)
DG_Ran DGEdit(DG_Ran *g,DG_Num pos,DG_Num n,DG_Ran val)
{
DG_Num f = DGFather(pos);
DG_Ran o = *( g + pos );
*( g + pos ) = val;
if(f < n)
{
DG_Ran fv = val - o + *( g + f );
DGEdit(g, f, n, fv);
}
return n;
}
//树状数组的翻转(树状数组的应用)
//一维 复杂度log(n)
//小于等于指定位置的元素的翻转<=pos
void DGDown1(DG_Ran g[],DG_Num pos,DG_Ran av)
{
while(pos >= 0)
g[pos] += av , pos = DGBrother(pos);
}
//获取位置pos的元素翻转次数
DG_Ran DGCUp1(DG_Ran g[],DG_Num pos , DG_Num n)
{
DG_Ran t = 0;
while(pos < n)
t += g[pos] , pos = DGFather(pos);
return t;
}
//二维 复杂度(log(n))^2
//小于等于指定位置的元素的翻转(0,0)->(x,y)
void DGDown2(DG_Ran g[][DG_MAXN],DG_Num x ,DG_Num y,DG_Ran av)
{
while(x >= 0)
{
DG_Num tmp = y;
while (tmp >= 0)
{
g[x][tmp] += av;
tmp = DGBrother(tmp);
}
x = DGBrother(x);
}
}
//获取位置(x,y)的元素翻转次数
DG_Ran DGCUp2(DG_Ran g[][DG_MAXN],DG_Num x ,DG_Num y , DG_Num n)
{
DG_Ran t = 0;
while(x < n)
{
DG_Num tmp = y;
while (tmp < n)
{
t += g[x][tmp];
tmp = DGFather(tmp);
}
x = DGFather(x);
}
return t;
}