As usual, Alice finishes her delicious cake at noon. Unfortunately, the smell of cake beckoned hungry Bob, and he decided to rob one piece of cake.
The cake is a convex polygon with N edges. At the beginning, Bob cut it along the diagonals. After M cuts, Bob decided to rob the 'largest' piece of cake. Strangely, in Bob's opinion, the piece has the most number of edge is the biggest one.
Please help Bob to find the 'largest' piece.
Input
There are multiple test cases (about 20).
The first line of each test case contains two integer number N, M (5 <= N <= 10000), indicating the number of point of the cake and the cut, respectively.
The following M lines contain two integer x, y (1 <= x, y <= N), denoting the index of the starting and ending cut point. (the index of points mark from 1 to N clockwise.)
The input will guarantee that all of the cuts will not intersect inside the cake, but they may cross each other at the edge of cake, and Bob won't cut along the initial edge of the cake.
Output
Output the maximal size (most number of edges) of the piece which Bob will get.
Sample Input
7 2
3 6
7 2
Sample Output
4

// 还没想通
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 20010
using namespace std;
struct data
{
    int l, r, s;
    data(int _l, int _r, int _s) : l(_l),r(_r),s(_s){}
    data(){}
}d[N];
bool cmp(data a, data b)
{
    return a.s < b.s;
}
int next[N], n, m;
int main()
{
    while (scanf("%d%d", &n, &m)!= EOF)
    {
        int x, y;
        for (int i = 1; i < 2 * n; ++i)
            next[i] = i + 1;
        next[2 * n] = 1;
        for (int i = 1; i <= m; ++i)
        {
            scanf("%d%d", &x, &y);
            if (x > y) swap(x, y);
            int l = y - x + 1;
            if (l > n - l + 2)//?
            {
                int temp = x; x = y; y = temp + n;
                l = n - l;
            }
            d[i] = data(x, y, l);
        }
        sort(d + 1, d + 1 + m, cmp);
        int res = 0, sum = n;
        for (int i = 1; i <= m; ++i)
        {
            int l = 0, s = d[i].l;
            while (s != d[i].r)
            {
                s = next[s], l++;
            }
            res = max(res, l + 1);
            sum -= (l - 1);
            next[d[i].l] = d[i].r;
            if ((d[i].l <= n) && (d[i].r <= n)) next[d[i].l + n] = d[i].r + n;
            else next[d[i].l + n] = d[i].r - n;
        }
        res = max(res, sum);
        printf("%d\n", res);
    }
    return 0;
}

        Arcgis for Android的地图操作里，放大缩小地图、图层切换、定位、测距测面等都是它的一些基本操作，封装后一般调用就是了，很简单。不过最近有了个需求，在地图上画一个多边形时候同时进行多边形的边长、周长和面积的计算，于是重新又写了下这个方法。代码不难，但是觉得挺有意思，于是写博文记录一下。
        首先，需要在地图上画多边形。我们看到的每个地图都是一个图层，要在地图上画个多边形，就是在图层上加载一个图形，而这个图形就是用Graphic类来实现的。从Graphic最简单的构造函数：

public Graphic(Geometry geometry, Symbol symbol) 
        我们可以看出，它主要由一个Geometry和一个Symbol构成。Geometry代表着所有0.1.2维几何图形，常用的包含了Point（点），Line（线段），Polyline（折线），Polygon（面）等。Symbol代表着这些几何图形的样式，比如点线面的大小和颜色等。

        了解了基本信息以后，首先要执行的是点击地图画多边形，点击事件是：

mMapView.setOnSingleTapListener(new OnSingleTapListener() {
    @Override
    public void onSingleTap(float v, float v1) {
        PointToDrawPolygon(v, v1);
    }
});
         传的两个参数分别是屏幕的坐标。

         然后就是画多边形了。首先每次先要把图层清空一下，如果不清空，将会保留之前画的图形。想象一下，就是比如我们第三个点时候画了一个三角形，然后按第四个点时候画了一个四边形，如果不清空的话，就是四边形覆盖在三角形上的样子。

if (messureGraphicsLayer!=null){
    messureGraphicsLayer.removeAll();
}
        接下来是将屏幕点转为地图上的点，并设置样式画上去：


Point mPoint = diitMapView.toMapPoint(v, v1);//选择点
mPoints.add(mPoint);//选择点加入点的集合
Graphic messurePoint = new Graphic(mPoint, symbolFactory.createMeasureMarkerSymbol());//点的要素初始化
messureGraphicsLayer.addGraphic(messurePoint);//点的要素添加到图层
        这里说下Symbol类，主要有一下几种：



         然后是进行判断，设置面的初始点，以及将之后各个点连接成折线和面：

if (mPoints.size() == 1) {
    messurePolygon.startPath(mPoints.get(0));//设置面的初始点
}
if (mPoints.size() > 1) {
    messureGraphicsLayer.removeAll();
    messurePolyline.setEmpty();
    messurePolygon.lineTo(mPoint);//连接到当前点击的点
    messurePolygon.lineTo(mPoints.get(0));//连接到初始点
    for (int i = 0; i < mPoints.size() - 1; i++) {
        messureLine.setStart(mPoints.get(i));
        messureLine.setEnd(mPoints.get(i + 1));
        messurePolyline.addSegment(messureLine, true);
        messureGraphicsLayer.addGraphic(new Graphic(mPoints.get(i), symbolFactory.createMeasureMarkerSymbol()));
    }
    messureGraphicsLayer.addGraphic(new Graphic(mPoints.get(mPoints.size() - 1), symbolFactory.createMeasureMarkerSymbol()));
    messureLine.setStart(mPoint);
    messureLine.setEnd(mPoints.get(0));
    messurePolyline.addSegment(messureLine, true);
    Graphic messureLineGraphic = new Graphic(messurePolyline, symbolFactory.createMeasureLineSymbol());
    Graphic messureAreaGraphic = new Graphic(messurePolygon, symbolFactory.createMeasureFillSymbol());//初始化面的要素
    messureGraphicsLayer.addGraphic(messureAreaGraphic);//将面的要素添加到图层
    messureGraphicsLayer.addGraphic(messureLineGraphic);
    messurePolygon.startPath(mPoint);//将当前点设为初始点
}
        接下来就是要计算边长、周长和面积了。基本原则是这样的，用Line计算边长，用Polyline计算周长，用Polygon计算面积，计算时候也注意下最后一个边：


 if (mPoints.size() > 1) {
        messureLine.setStart(mPoints.get(mPoints.size() - 2));//将上一个点作为起始点
        messureLine.setEnd(mPoints.get(mPoints.size() - 1));//将该点作为终止点
        messurePolyline.addSegment(messureLine, true);//将线段加入到线段组
        Graphic messureLineGraphic = new Graphic(messurePolyline, symbolFactory.createMeasureLineSymbol());//将线段组变为线段要素
        TextSymbol ts = new TextSymbol(16,String.format("%.2f", messureLine.calculateLength2D())+"m",Color.BLACK);
        Polyline line=new Polyline();
        line.addSegment(messureLine,true);
        Graphic textGraphic=new Graphic(line,ts);
        listgraphic.add(textGraphic);
        for(Graphic graphic:listgraphic) {
            messureGraphicsLayer.addGraphic(graphic);
        }
        messureGraphicsLayer.addGraphic(messureLineGraphic);//将线段组要素添加到图层
        messureDistance += messureLine.calculateLength2D();//累计计算线段长度
        tvMessureResult.setText("长度："+String.format("%.2f", messureDistance) + "m");//文本设置长度
        showMessureResult(tvMessureResult, mPoint);//显示出来
    }
    if (mPoints.size() > 2) {
        Line lastLine=new Line();
        lastLine.setStart(mPoints.get(mPoints.size() - 1));
        lastLine.setEnd(mPoints.get(0));
        Polyline lastPolyline=new Polyline();
        lastPolyline.addSegment(lastLine,true);
        TextSymbol ts = new TextSymbol(16,String.format("%.2f", lastPolyline.calculateLength2D())+"m",Color.BLACK);
        Graphic textGraphic=new Graphic(lastPolyline,ts);
        messureGraphicsLayer.addGraphic(textGraphic);
        double messureArea = messurePolygon.calculateArea2D();//计算面积
        tvMessureResult.setText("周长："+String.format("%.2f", messureDistance+lastLine.calculateLength2D()) + "m"+"\n"+"面积："+String.format("%.2f", Math.abs(messureArea)) + "㎡");//设置面积文本
        showMessureResult(tvMessureResult, mPoint);
    }

题目：
    在直角坐标系平面上，给定一些点（个数大于2），这些点组成一个多边形。
    给定一个数字k(k>=2),将多边形的边长平分成k份。
   输出：k个点，这些点全部都是多边形上的。
 
我的思路如下：
    先求出总长度，然后求出平均长度。
   第一个点取输入的第一个顶点。
   具体过程看我源代码(Java)：
 
package com.learing.divingpolygon;
public class PolygonDivider {
 /**

  * Divide input polygon into parts evenly by side length.

  * @param pts    Input points.

  * @param numOfParts  How many parts to be divided to.

  * @return null if failed, otherwise the points on polygon.

  */

 public static Point [] divide(Point [] pts, int numOfParts) {

  if (numOfParts <= 1 || pts == null || pts.length < 2) {

   return null;

  }

  

  // the part length.

  final float partLen = getDividingLen(pts, numOfParts);

  

  Point [] result = new Point[numOfParts];

  

  // set the first result point as pts[0].

  result[0] = pts[0];

  

  // count of currently found results.

  int count = 1;

  

  // index for source points.

  int sourceIndex = 1;

  

  // the current point from where to calculate.

  Point cur = pts[0];

  

  // accumulated length for current point calculation.

  float accumulated = 0.0f;

  

  while (true) {

   if (sourceIndex >= pts.length) {

    System.err.print("program error.");

    return null;

   }

   Point dest = pts[sourceIndex];

   float distance = getDistance(cur, dest);

   if (distance < partLen - accumulated) {

    cur = dest;

    accumulated += distance;

    ++sourceIndex;

    

    // the last segment 's target is the original point.

    // here the original point is set to the first point.

    if (sourceIndex == pts.length) {

     sourceIndex = 0;

    }

   } else {

    cur = getPointByDistance(cur, dest, partLen - accumulated);

    accumulated = 0.0f;

    result[count++] = cur;

    if (count == numOfParts) {

     break;

    }

   }

  }

  

  return result;

 }

 

 static float getDividingLen(Point [] pts, int numOfParts) {

  float sum = 0.0f;

  final int n = pts.length;

  for (int i = 1; i < n; ++i) {

   sum += getDistance(pts[i - 1], pts[i]);

  }

  

  float lastLen = getDistance(pts[n - 1], pts[0]);

  sum += lastLen;

  return sum / numOfParts;

 }

 

 /**

  * Get a float point on segment(from start to end) which satisfies that

  * the length between start and the point is len. 

  * @param start

  * @param end

  * @param len

  * @return the point which satisfies 

  * that the length between start and the point is len.

  */

 static Point getPointByDistance(Point start, Point end, float len) {

  // special occasion : vertical line, the slant ratio doesn't exist.

  if (start.x == end.x) {

   return new Point(start.x, end.y > start.y ? start.y + len : start.y - len);

  }

  

  final float slant = (end.y - start.y) / (end.x - start.x);

  

  // result point x:

  float x = end.x > start.x ?

    len / (float) Math.sqrt(1 + slant * slant) + start.x

    : -len / (float) Math.sqrt(1 + slant * slant) + start.x;

  

  // result point y:

  float y = start.y + slant * (x - start.x);

  

  return new Point(x, y);

 }
 private static float getDistance(Point pt1, Point pt2) {

  return (float) Math.hypot(pt2.x - pt1.x, pt2.y - pt1.y);

 }

 

}
 
测试代码如下：
  @Test

 public void testDividing() {

  Point pts[] = new Point[] {

    new Point(0, 0),

    new Point(10, 0),

    new Point(10, 10),

    new Point(0, 10),

  };

  

  Point [] result = PolygonDivider.divide(pts, 5);

  

  Assert.assertEquals(result.length, 5);

  Assert.assertEquals("assert equals", result[0].x, 0, 0.01f);

  Assert.assertEquals("assert equals", result[0].y, 0, 0.01f);

  

  Assert.assertEquals("assert equals", result[1].x, 8, 0.01f);

  Assert.assertEquals("assert equals", result[1].y, 0, 0.01f);

  

  Assert.assertEquals("assert equals", result[2].x, 10, 0.01f);

  Assert.assertEquals("assert equals", result[2].y, 6, 0.01f);

  

  Assert.assertEquals("assert equals", result[3].x, 6, 0.01f);

  Assert.assertEquals("assert equals", result[3].y, 10, 0.01f);

  

  Assert.assertEquals("assert equals", result[4].x, 0, 0.01f);

  Assert.assertEquals("assert equals", result[4].y, 8, 0.01f);

 }


 
 

POJ 1788 Building a New Depot(计算正多边形边长)
http://poj.org/problem?id=1788
题意: ZOJ 2157
       有一个多边形(可能是凹或凸),这个多边形的每条边都平行于坐标轴,且给出多边形所有顶点的坐标,每个顶点都是拐点(即连接该顶点的两边肯定相互垂直),现在要你输出该多边形的周长.
分析:
       由于题目给出的该多边形的限制条件:平行坐标轴,每个点都是拐点. 那么可以得出结论: 

对于每个X或Y坐标,该坐标上多边形的顶点数目一定是偶数个.(假设x=5坐标有多个顶点,那么顶点数一定是偶数,比如2个或4个或6个,不可能是奇数个)
       对于某个坐标值X(或Y),如果该坐标值有偶数个点,那么该坐标上肯定有边,且从上到下相邻的两个点互连成边.如下图:
 

       对于上图,可以自己对于用例画画,验证一下.
       由上面两条结论,我们可以知道每个有多边形点的x或y坐标的边构造必然是: 坐标相邻的两个点连接成一条边即可,所以我们只要加上所有这些边即可.
       首先把所有点坐标按X值排序,算出同一X值上的所有竖直的边长.
       然后把所有点坐标按Y值排序,算出同一Y值上的所有水平的边长.
       所有边长相加输出周长即可.
AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100000+10;
struct Point
{
    int x,y;
}P[maxn];
bool compare_x(Point A,Point B)//升序排列
{
    return A.x<B.x || (A.x==B.x&&A.y<B.y);
}
bool compare_y(Point A,Point B)
{
    return A.y<B.y || (A.y==B.y&&A.x<B.x);
}


int main()
{
    int n;
    while(scanf("%d",&n)==1 && n)
    {
        for(int i=0;i<n;++i) scanf("%d%d",&P[i].x,&P[i].y);
        int ans=0;
        sort(P,P+n,compare_x);
        for(int i=0;i<n;)
        {
            if(P[i].x==P[i+1].x)//计算竖直边
            {
                ans += P[i+1].y-P[i].y;
                i+=2;
            }
            else ++i;
        }
        sort(P,P+n,compare_y);
        for(int i=0;i<n;)
        {
            if(P[i].y==P[i+1].y)//计算水平边
            {
                ans+= P[i+1].x-P[i].x;
                i+=2;
            }
            else ++i;
        }
        printf("The length of the fence will be %d units.\n",ans);
    }
    return 0;
}