专栏首页HansBug's Lab算法模板——计算几何2(二维凸包——Andrew算法)

算法模板——计算几何2(二维凸包——Andrew算法)

实现功能:求出二维平面内一对散点的凸包(详见Codevs 1298)

很神奇的算法——先将各个点按坐标排序,然后像我们所知的那样一路左转,求出半边的凸包,然后反过来求另一半的凸包

我以前正是因为总抱着想一步到位的想法,所以每次都跪得很惨(HansBug:事实上这次是我这辈子第一次A掉凸包题)

然后别的没了,就是凸包的基本思想

(顺便输出凸包周长C和面积S)

 1 type arr=array[0..100005] of longint;
 2 var
 3    i,j,k,l,m,n,m1,m2:longint;
 4    a:array[0..100005,1..2] of longint;
 5    b,c,d:arr;ans,are:extended;
 6 procedure swap(var x,y:longint);
 7           var z:longint;
 8           begin
 9                z:=x;x:=y;y:=z;
10           end;
11 procedure sort(l,r:longint);
12           var i,j,x,y:longint;
13           begin
14                i:=l;j:=r;x:=a[(l+r) div 2,1];y:=a[(l+r) div 2,2];
15                repeat
16                      while (a[i,1]<x) or ((a[i,1]=x) and (a[i,2]<y)) do inc(i);
17                      while (a[j,1]>x) or ((a[j,1]=x) and (a[j,2]>y)) do dec(j);
18                      if i<=j then
19                         begin
20                              swap(a[i,1],a[j,1]);
21                              swap(a[i,2],a[j,2]);
22                              inc(i);dec(j);
23                         end;
24                until i>j;
25                if i<r then sort(i,r);
26                if l<j then sort(l,j);
27           end;
28 function right(x1,y1,x2,y2:longint):boolean;
29          begin
30               exit((x1*y2)>(x2*y1));
31          end;
32 function trip(x1,y1,x2,y2,x3,y3:longint):boolean;
33          begin
34               exit(right(x2-x1,y2-y1,x3-x2,y3-y2));
35          end;
36 function check(x,y,z:longint):boolean;
37          begin
38               exit(trip(a[x,1],a[x,2],a[y,1],a[y,2],a[z,1],a[z,2]));
39          end;
40 procedure doit(var b:arr;var m:longint);
41           begin
42                b[1]:=d[1];b[2]:=d[2];j:=2;
43                for i:=3 to n do
44                    begin
45                         while (j>1) and not(check(b[j-1],b[j],d[i])) do dec(j);
46                         inc(j);b[j]:=d[i];
47                    end;
48                m:=j;
49           end;
50 begin
51      readln(n);
52      for i:=1 to n do readln(a[i,1],a[i,2]);
53      sort(1,n);j:=1;
54      for i:=2 to n do  //去重
55          begin
56               if (a[i,1]<>a[j,1]) or (a[i,2]<>a[j,2]) then
57                  begin
58                       inc(j);
59                       a[j,1]:=a[i,1];a[j,2]:=a[i,2];
60                  end;
61          end;
62      n:=j;
63     //求凸包
64      for i:=1 to n do d[i]:=i;doit(b,m1);
65      for i:=1 to n do d[i]:=n+1-i;doit(c,m2);
66     //两个半边整合
67      for i:=1 to m1 do d[i]:=b[i];
68      for i:=2 to m2 do d[i+m1-1]:=c[i];
69     //开始计算周长+面积
70      m:=m1+m2-2;ans:=0;are:=0;
71      for i:=1 to m do ans:=ans+sqrt(sqr(a[d[i],1]-a[d[i+1],1])+sqr(a[d[i],2]-a[d[i+1],2]));  //周长
72      for i:=1 to m do are:=are+a[d[i],1]*a[d[i+1],2]-a[d[i],2]*a[d[i+1],1];  //面积
73      are:=abs(are)/2;
74      writeln('Convex Hull:');
75      for i:=1 to m do writeln(a[d[i],1],' ',a[d[i],2]);
76      writeln('C = ',ans:0:1);
77      writeln('S = ',are:0:1);
78      readln;
79 end.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 1601: [Usaco2008 Oct]灌水

    1601: [Usaco2008 Oct]灌水 Time Limit: 5 Sec  Memory Limit: 162 MB Submit: 1342  S...

    HansBug
  • 1609: [Usaco2008 Feb]Eating Together麻烦的聚餐

    1609: [Usaco2008 Feb]Eating Together麻烦的聚餐 Time Limit: 10 Sec  Memory Limit: 64 M...

    HansBug
  • 2818: Gcd

    2818: Gcd Time Limit: 10 Sec  Memory Limit: 256 MB Submit: 2170  Solved: 979 [Su...

    HansBug
  • 1601: [Usaco2008 Oct]灌水

    1601: [Usaco2008 Oct]灌水 Time Limit: 5 Sec  Memory Limit: 162 MB Submit: 1342  S...

    HansBug
  • 算法-买卖股票的最佳时机 II

    版权声明: ...

    Fisherman渔夫
  • 3522: [Poi2014]Hotel

    3522: [Poi2014]Hotel Time Limit: 20 Sec  Memory Limit: 128 MB Submit: 253  Solve...

    HansBug
  • 2292: 【POJ Challenge 】永远挑战

    2292: 【POJ Challenge 】永远挑战 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 553 ...

    HansBug
  • 1131: [POI2008]Sta

    1131: [POI2008]Sta Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 783  Solved:...

    HansBug
  • matlab绘图(一)

    matlab除了强大计算功能之外,其绘图功能也是不容小觑的。平时大家计算的结果常常需要以图形的方式给他人展示,今天就给大家介绍几个matlab最基本的二维绘图命...

    艾木樨
  • Spring源码-父子容器

    秋日芒草

扫码关注云+社区

领取腾讯云代金券