acm计算几何基础题目

1、poj 1113 wall计算几何，求凸包这题的结果等于这个多边形构成的凸包的周长加上以所给半径为半径的圆的周长步骤如下：1）算法首先寻找最最靠下方的点，如果遇到y坐标相同，则寻找x坐标最小的点firstp2）然后根据所有点相对于firstp的偏角的大小进行排序，遇到偏角相等的，只取距离 firstp最远的点（排序利用自己手写的快排）3）然后利用graham算法求凸包4）最后直接求职#include <iostream> #include <cmath>#define pi 3-1415926 #define max n 1000 using namespace std

2、;存储原始输入的坐标值，tad是输入的半径 double cordmax n + 2 2, rad;int seqmax_n + 2;int stackmax n + 2;int n, top;int firstp;int realn;void swap(int posl, int pos2)int temp = seqposl;seqtposl = seqpos2;seqpos2 = temp;int dir(int nodes, int nodel, int node2)double double double returnxl = cordnodel 0, x2 = cordnode20

3、, cordnodes 0,(x2 - sx) * (yl - sy) 一sx 二yiy2sy=cordnode11;=cordnode21;=cordnodes1;(xl 一 sx) * (y2 一 sy);double getdist (int nodel, int node2)double xl = cordnodel0, yl = cordnode叮1; double x2 = cordnode20, y2 = cordnode21;double res = sqrt(xl - x2)* (xl 一 x2) + (yl 一 y2) * (yl 一 y2);return res;int

4、compare(int nodel, int nodc2)double xl = cord node10, yl = cordnode11; double x2 = cordnode20, y2 = cordnode21;double sx = cordfirstp0, sy = cordfirstp1;double type = dir(firstp, nodol, node2);if (type = 0)double distl = (xl - sx) * (xl - sx) + (yl - sy) * (yl - sy); double dist2 二(x2 - sx) * (x2 一

5、sx) + (y2 一 sy) * (y2 - sy); if(distl > dist2)return -2;else if(distl = dist2)return 0;elsereturn 2;else if(type > 0)return 1;elsereturn t;void fastsort(int start, int end)i f (start < end)int curpos = start;int poss = start, pose = end + 1;while(true)while(compare(seq+poss, seqcurpos) <

6、 0 && poss < end); while(compare(seq-pose, seqcurpos) > 0 && pose > start); if (poss < pose)swap(poss, pose);elsebreak;swap(curpos, pose); fastsort(start, pose - 1); fastsort(pose + 1, end);void sortseqoint i, s = 0;for(i = 1; i <= n; i+)/最低最左点不参加排序 if(i = firstp)conti

7、nue;seq+s = i;realn = n - 1;fastsort (1, realn);/清理夹角相同但是距离不同的点，只取举例firstp最远的点i = 1;while(i < realn)s = i + 1;/equal angle but smaller distaneewhile(s <= realn && compare(seqi, seqs) = -2)seqs = -1; /置为无效s+;i = s;/寻找凸包void findq()int nodes, nodel, node2, type;top = 0;stacktop+二 firstp;

8、int s = 1;int c = 0;while(c < 2)if(seqs != -1)c+;stacktop+ = seqs;s+;for(; s <= realn; s+)if(seqs = t)continue;wh i1e (true)nodes = stacktop - 2;nodel = stacktop - 1;node2 = seqs;type = dir(nodes, nodel, node2);if (type >= 0)top;elsebreak;stacktop+ = seqs;double getres ()double totaldist =

9、0;int lastnode = firstp;int curnode;while (top > 0)curnode = stacktop;totaldist +二 getdist(lastnode, curnode);lastnode = curnode;/totaldist += getdist(lastnode, firstp);totaldist +二 2 * pi * rad;return totaldist;int main()int i:cin»n»rad;int minx = int_max, miny = int_max;for(i = 1; i &

10、lt;= n; i+)cin»cordi 0»cordi 1;if(cordi1 < miny) | (cordi1 = miny && cordi0 < minx)firstp = i; minx = cordi0;miny 二 cordi 1;sortseq ();findqo;double res 二 getres(); printf ("%. ofn/z, res); return 0;poj1292 will indiana jones get there?题目大意：英雄jones现在在位置1,有人在位置2呼救，所以他要过去救

11、他，但是有个条 件，他必须在墙上走，其实就是说他只能在图示的线段上走，但是线段间有空隙，所以要用 一个t板搭在线段间才能从一个线段到另外一个线段，问怎么找到一个路径使得要使用的长 板最小。题目一眼看下去还比较复杂，毕竟你看到是一堆线段，但是这时候一个很直观的思想就是枚 举两个线段间的距离，将每个线段都看成是一个节点，这样其实就化为了一个简单的有向图, 这时要寻找最短的反板其实最小生成树的问题，利用ivim算法就可以解决，本题的难处就 在于计算线段i'可的距离跟最小生成树的实现。计算线段i'可距离写得很乱，大家包容。include <math. h>#include

12、<memory. h>#inelude <stdio. h>float hordist( int xl, int yl, int li, int x2, int y2, int l2 )if ( x2 > xl )if ( x2 > xl+ll )return sqrt(float)(x2 - xlll)*(x2 - xl-ll) + (y2 - yl)*(y2 - yl);elsereturn abs( y2 - yl );elseif ( xl > x2 + l2)return sqrt(float) (xl - x2-l2)*(xl - x2-l

13、2) + (y2 - yl)*(y2 - yl);el sereturn abs( y2 - yl ); float verdist( int xl,int yl, int li, int x2, int y2, int l2 )return hordist( yl, xl,-li, y2, x2, -l2 );float hor2verdist( intxl,int yl, int li, int x2, int y2, int l2 )int xhor, if ( li >yhor, lhor,0 )xver,yver, lver;xhor 二 yllor = lhor = xver

14、 = yver =lver =xl;yl;li;x2;y2;72;elsexhor = yllor =li lor = xver = yver = lver =x2;y2；l2;xl; yl;li;if ( yver<=yhor &&yhor<=(yver+lver)if ( xhor <= xver&& xver<= (xhor+lhor)return 0.0;elseif ( xver > (xhor+lhor)return xver 一 xhor- lhor;elsereturn xhor - xver;elseif ( xh

15、or <= xver && xver<= (xhor + lhor)if ( yllor > (yver+ lver)return yhor - yver 一 lver;elsereturn yver - yllor;elseif ( xver > (xhor+lhor)if ( yhor > (yver+ lver)return sqrt(float)(pow(float)(yhor - yver - lver), 2)+pow(float)(xver - xhor - lhor), 2 );elsereturn sqrt (float) (po

16、w(float) (yllor - yver) , 2) +pow( (float) (xver - xhor - lhor), 2 );elseif ( yllor > (yver+ lver)return sqrt(float) (pow(float) (yhor - yver - lver), 2)+pow( (float)(xver 一 xhor) , 2 );elsereturn sqrt (float) (pow( (float) (yhor - yver) , 2) +pow ( (float) (xver - xhor), 2 );template<class t

17、>t minfloat( const t &a, const t&b )return (a<b)?a:b;；float dist ( int xl, int yl, int li, int x2, int y2, int l2 )if ( li = 0 )if ( l2 = 0 )return sqrt (float) (pow(float) (xl-x2), 2)+pov(float) (yl-y2), 2);else if ( l2 < 0 )int ytemp = 0;int xtemp = 0;ytemp = y2-l2;xtemp = x2;if (

18、 y2 <= yl && yl <= ytemp )return abs( xl-x2 );elsereturn minfloat(sqrt(float)(pow(float)(xl-x2), 2)+pow(float)(yl-y2), 2), sqrt(float)(pow(float)(xl-xtemp), 2)+pow(float)(yl-ytemp), 2);el seint ytemp = 0;int xtemp = 0;ytemp = y2;xtemp = x2+l2;if ( x2 <= xl && xl <= xtemp

19、)return abs( yly2 );elsereturn minf 1 oat(sqrt(float)(pow(float)(xlx2), 2)+pow(float)(yl-y2),2), sqrt(float)(pow(float)(xl-xtemp), 2)+pow(float)(yl-ytemp), 2);if ( l2 二二 0 )if ( ll= 0 )return sqrt (float) (pow(float) (xl-x2), 2)+pov(float) (yl-y2), 2);else if ( li < 0 )int ytemp = 0;int xtemp = 0

20、;ytemp = ylll;xtemp = xl;if ( yl <= y2 && y2 <= ytemp )return abs( xlx2 );elsereturn minfloat(sqrt(float)(pow(float)(xl-x2), 2)+pow(float)(yl-y2), 2), sqrt(float)(pow(float)(x2-xtemp), 2)+pow(float)(y2-ytemp), 2);el seint ytemp = 0;int xtemp = 0;ytemp = yl;xtemp = xl+ll;if ( xl <= x

21、2 && x2 <= xtemp )return abs( yl-y2 );elsereturn minfl oat(sqrt(float)(pow(float)(xl-x2), 2)+pow(float)(yl-y2), 2), sqrt(float)(pow(float)(x2-xtemp), 2)+pow(float) (y2-ytemp)，2);if ( l1*l2if ( lireturnelsehordist ( xl, yl, li, x2, y2, l2）；returnverdist( xl, yl, li, x2, y2, l2）；elsereturn

22、hor2verdist( xl, yl, li, x2, y2, l2 );constcons tfloat struct wallint maxvalue = 1005;float maxfloat = 10000000000.0;di st array maxval ue maxva.1 ue ;int x;int y;int length;wall walls maxvalue ;struct pointinfoint parent; float path; bool goon; bool complete;pointtnfo info maxvalue ; float prim( in

23、t n )int i;wh i1e ( true )float minvalue = maxfloat;int minindex = t;for ( i = 0; i < n; +i )if ( info i . goon && !info i . complete )if ( infoi.psth < minvalue )minvalue = info i . path;minlndex 二 i;info minlndex . complete = true;if ( minlndex = 1)break;for ( i = 0; i < n; +i )if

24、 ( !info i .complete && i != minlndex )info i .goon = true;if (distarray minlndex i < info i .path ) info i .path = di starray minlndex i ; info i . parent = minlndex;float length = 0. 0;i = 1;while( info i . parent != -1 )float temp = distarray infoi.parent i ;if ( length < temp )1eng

25、th = temp;i = info i .parent;return length;int mdino while( true )int n;int i;int j;break;for ( i = 0; i < n; +i )scanf ("%d %d %d", &walls i . x, &walls i . y, &walls i . length);memset( distarray, 0, sizeof (distarray);for ( i = 0; i < n; +i )for ( j = i+1; jn;卄j )di st

26、array i walis j < x, wallsdistarray j .length,=di st ( wal 1 s i x, wal 1 s i . y, wal ls y, walis j .length );二 distarray i j ;for ( i = 1; i < n; +i )info i j.path 二 maxfloat;info i goon 二 false;info i . complete = false;info i parent = 0;info 0 .path = 0;info 0 .goon = true;info 0 .complete

27、 = false;info 0 .parent = t; float length = prim( n ); printf c%. 2fn，z, length );return 0;poj2148color the map线段部分重合本题如果把图建完了，其实就是枚举总颜色数后dfs即可。所以本题的关键就是建图啦。而建图重耍的是解决two countries are considered to be "adjacent" if any of their territories share a border of non-zerolength.亦即解决两条线段部分重合的问题。解

28、决部分重合的代码如下：int cross (const int &ax, const int &ay, const int &bx, const int &by)return ax*by-bx*ay;int dot (const int &ax, const int &ay, const int &bx,const int &by)return ax*bx+ay*by;bool covered (const int &pax, const int &pay, const int &pbx, const in

29、t &pby, const int&qax,const int &qay,const int &qbx,const int &qby)if (cross(pax-pbx, pay-pby, qax-qbx, qay-qby)!=0) return 0;i f (pax=qax&&pay二二qay&&pbx二二qbx&&pby二二qby)/printf (/z#lnz/);return 1;i f (pax二二qbx&&pay二二qby&&pbx二二qax&&p

30、by二二qay)/printf (/z#2nz/);return 1;if(cross(pax-qax,pay-qay, pax-qbx, pay-qby)=0&&dot (pax-qax, pay-qay, pax-qbx, pay-qby )<0)/printf("#3n");return 1;if(cross(pbx-qax, pby-qay, pbx-qbx, pby-qby)二二0&&dot(pbx-qax, pby_qay, pbx-qbx,pby-qby)<0)/printf("#4n");ret

31、urn 1;if(cross(qax-pax,qay-pay, qax-pbx, qay-pby)=二0&&dot(qax-pax, qay-pay, qax-pbx, qay-pby )<0)/printf("#3n");return 1;if(cross(qbx-pax, qby-pay, qbx-pbx, qby-pby)二二0&&dot(qbx-pax, qby-pay, qbx-pbx, qby-pby)<0)/printf c#4n/z);return 1;return 0;poj 2653 pick-up stick

32、s题目大意：给定一堆筷子，依次往下抛，给定筷子的两断点坐标，求哪些筷子在最上面(即 那些筷子上面没有其他筷子压着)思路：判断线段相交，用叉积。设p=(xl, yl), q=(x2, y2),则pxq二xl*y2-x2*yl,若pxq为正数,则对于原点来说,p在q的 顺时针方向上；若pxq为负数，则p在q的逆时针方向上。对于有公共断点的三条线段来说, 设该三条线段的向量分别为pl, p2, p3,假设p2在pl的逆时针方向上，p3在pl的顺时针方 向上,那么(p2xpl)*(p3xpl)必定小于0o#include<stdio.h> #include<stdlib. h>

33、 define eps le-9 struct pointdouble x, y;struct linepoint pl, p2;；line line100002;double max (double a, double b)return a>b?a:b;double min(double a, double b)return a>b?b:a;double mulit(point po,point pl, point p2)return (pl. x-po. x) * (p2. y-po. y) - (p2. x-po. x) * (pl. y-po. y); int cross

34、(line a, line b) /判断两线段是否相交if (max (a. pl. x, a. p2. x) >min (b. pl. x, b. p2. x)&&max(b. pl. x, b. p2. x) >min(a. pl. x, a. p2. x)&&max (a. pl. y, a. p2. y) >mtn(b. pl. y, b. p2. y)&&max (b. pl. y, b. p2. y) >min(a. pl. y, a. p2. y)&&mulit (a. pl, a. p2,

35、b. pl)*mul it (a. pl, a. p2, b. p2) <eps&&mulit (b. pl, b. p2, a. pl)*mulit (b. pl, b. p2, a. p2) <eps) return 1;return 0;int main(void)int n, i, j；while (1)scanf ("%d", &n);if(n=0)break;for (i=l;i<=n;i+)scanf (，z%lf %lf %1 f %l f",&linei pl. x, &linei. pl

36、. y, &1 inei. p2. x, &linei. p2. )；printf(，ztop sticks:");for(i=l;i<=n-l;i+)for(j=i+l;j<=n;j+)if(cross(linei, linej)break;if(j=n) /若没有其他筷子与其相交，则该筷子是最上面筷子之一printf (" %d, “，i);printf (“ %d. n", n);return 0;poj 1584 a round peg in a ground hole给你一个多边形的n个顶点坐标，然后再给一个钉子，给定钉子的半

37、径和圆心坐标，首先判 断多边形是否为凸多边形，若为凸多边形，再判断钉子是否可以放到凸多边形内部。1判断是否为凸边变形，第一步将顶点逆时针排列，再根据pipj应在pi-lpi的逆时针方 向，若存在pipj在pi-lpj的顺时针方向，则该多边形为凹多边形。2.判断圆（钉子）是否在多边形内部，第一步判断圆心是否在凸多边形内部，第二步再判断圆 心到某一边的最短距离，若存在某最短距离大于圆心，则圆不能放在凸多边内。include <stdio. h>#include <math. h>#define eps le8struct pointdouble x, y;point ope

38、rator-(point p) point res;res x 二 x 一 p. x;res. y 二 y _ p. y; return res;struct circlepoint c;double r;double dis(point pl, point p2)point p3 二 p2 - pl;return sqrt (p3- x * p3. x + p3. y * p3. y);double multi(point pl, point p2)return pl. x * p2. y - ply * p2. x;void changedir(point p, int n)point i

39、mp;for(int i = 0;i < n / 2;i+)tmp = pi;pi = pn - i - 1;pn - i - 1 = tmp;double areaofploy(point p, int n)double area = 0 0;for(int i 二 0;i < n;i+)area +二 multi (pi, pi + 1); return area / 2;double areaofthree(point pl, point p2, point p3)return fabs(multi (p2 - pl, p3 - pl) / 2;void outpoint(point q)printf (，z (%. 21 f %. 21f) “，q. x, q. y);int isconvex(point p, int n) /* 判断是否凸多边形 */for(int i = l;in;i+)if (mul ti (pi % n - pi1, p(i + 1) % n - pi % n) < 0) return 0;return 1;int isinconvex (poin