TOI
Posted on 七月 14th, 2008.
给定一个多边形,求重心.其实只需要随便找一个点,然后围绕它分割成若干个三角形.三角形的重心可以用三顶点坐标的平均数表示,然后重心的权值就是三角形的有向面积.最后对重心坐标加权求平均数就行.不用管多边形是顺时针还是逆时针给出,也不用管是凸还是凹.
一定要记得,输出的时候加上一个eps!不然会有-0.00的诡异错误!我就是不听RoBa话输出时没加eps导致三个点WA掉…
{ TOI 1125; 搬石头 - sqybi’s code - 求多边形重心}//for my winstyprogram toi1125_sqybi; const fin = ’stone.in’; fout = ’stone.out’; nn = 1000000; eps = 1e-6;
var n, i: longint; a, b: array[1..nn]of record x, y: double; end; c: array[1..nn]of double; totx, toty, totn: double;
function crossMult(x1, y1, x2, y2: double): double; begin crossMult […]
Read Full Post |
Make a Comment ( 2 so far )
Posted on 七月 13th, 2008.
这里好久没更新了,因为没做什么太好的题.最近做题太少,这几天要开始努力做题了.
可以发现把城堡边界的凸包平移之后,多出来的拐角部分都是圆弧,而这些圆弧恰好可以组成一个圆.所以这道题的答案是凸包的周长+2*pi*l.第一次写凸包,发现没有想象的那么恶心,反而是异常好写.代码写得不好看,大牛忽略即可.
{ TOI 1149; 城堡围墙 - sqybi’s code - 凸包}//for my winstyprogram toi1149_sqybi; const fin = ‘wall.in’; fout = ‘wall.out’; nn = 1000; esp = 1e-6;
type rec = record x, y: double; end;
var n, i, sl1, sl2: longint; l, res: double; stack1, stack2: array[1..nn]of longint; a: array[1..nn]of rec;
function comp(a, b: […]
Read Full Post |
Make a Comment ( 2 so far )
Posted on 四月 19th, 2008.
又是KM的题目.对任意一对仓库和物资之间以距离的相反数为权值建边,然后KM.注意权值为负是因为需要求带权最小匹配.写的依然不熟,很诧异自己当时写了一次KM就一直没动过…忘得死死的.还好还有时间,最近复习好KM和HopCroft.似乎Dinic没法代替HopCroft…
{ TOI 1116; 运送物资 - sqybi’s code - 带权最小匹配 - KM}program toi1116_sqybi; const fin = ’snow.in’; fout = ’snow.out’; nn = 100;
var n, m, nx, ny, i, j, r: longint; ch: char; x, y: array[1..nn, 0..1]of longint; d: array[1..nn, 1..nn]of longint; match, lx, ly: array[1..nn]of longint; vx, vy: array[1..nn]of boolean;
function search(x: […]
Read Full Post |
Make a Comment ( None so far )
Posted on 三月 19th, 2008.
这道题是山东2007年第二次省选的题目,和这道题几乎一样的题目还在这些地方出现过:POJ 1733; URAL 1003; Vijos 1112; CEOI 99 Bugs.
看出现在这么多地方就知道应该是道很经典的题目了…
当时jl刚跟我说这道题,我就反应到了食物链那道题,但是后来jl说有mlogn的算法我就没向并查集方面想…后来发现的确是部分和+并查集,和我最开始的想法一样.算法复杂度O(m*alpha()),近似看作O(m).不过mlogn的算法没想出来.
首先,对于一个条件x y z,如果z=0,相当于转换为,对于一个只存有0和1的数组a[],a[x-1]和a[y]数组中存储的数相同.那么z=1就是存储的数不同.这里很好用部分和和奇偶性的知识解释,不赘述.这样,每次判断z,并判断x和y的关系,根据关系进行合并.用mark[x]记录树x的”敌人”(就是和a[x]存储的数不同的某一个位置–可以知道这个位置一定最多只有一个,多于一个时可以合并).
然后进行各种合并,具体方法看程序(主程序)中的判断部分.顺便判当前条件是否与之前的条件冲突.
这道题1Y,其实还是比较简单的,只不过判断的地方恶心了些,写到一半删了重写了一次…
{ TOI 1110; 01字符串问题 - sqybi’s code - 部分和+并查集}//for my winsty{$APPTYPE CONSOLE}program str_sqybi; const fin = ’str.in’; fout = ’str.out’; nn = 50000;
var n, m, i, x, y, z, fx, fy, t, total: longint; father, mark, size: array[1..nn+1]of longint;
function getF(x: longint): […]
Read Full Post |
Make a Comment ( None so far )