• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# 旋转卡壳算法

2周前 (04-30) 4次浏览

1.按照两个点去卡.(A)
2.按照一条边和边所对应的最远点去卡.(B)

…….

(有错误……)

import java.util.*;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
List<int[]> point = new ArrayList<int[]>();
int min = 0;
for(int i = 0;i<N;i++){ int[] s = new int[]{sc.nextInt(),sc.nextInt()}; point.add(s); if(point.get(min)[0]>s[0]){
min = i;
}
else if(point.get(min)[0] == s[0] && point.get(min)[1]>s[1]){
min = i;
}
}
final int[] compareP = new int[]{point.get(min)[0],point.get(min)[1]};
//点排序
Collections.sort(point, new Comparator<int[]>() {
public int compare(int[] ints, int[] t1) {
int[] vec1 = new int[]{ints[0]-compareP[0],ints[1]-compareP[1]};
int[] vec2 = new int[]{t1[0]-compareP[0],t1[1]-compareP[1]};
if(vec1[0]vec2[1]-vec1[1]vec2[0]>0){
return -1;
}
else if(vec1[0]vec2[1]-vec1[1]vec2[0]==0){
if(Math.pow(vec1[0],2)+Math.pow(vec1[1],2)-Math.pow(vec2[0],2)-Math.pow(vec2[1],2)>0){
return 1;
}
else{
return -1;
}
}
return 1;
}
});
//确定凸包
Stack stack = new Stack();
stack.push(0);
stack.push(1);
stack.push(2);

for(int i = 3;i<point.size();i++){ while(true){ int compareIndex = stack.pop(); int[] point0 = point.get(compareIndex); int[] point1 = point.get(stack.peek()); int[] point2 = point.get(i); int sinRes = sinZeroCompare(point1,point0,point2); if(sinRes>0){
stack.push(compareIndex);
break;
}
}
stack.push(i);
}

List<int[]> pointSideList = new ArrayList<int[]>();
while (!stack.isEmpty()){
}
int tempSquare = -1;
int pointCnt = pointSideList.size();
int compareStartIdx=2;
double maxDist = -1;
for(int i = 0;i<pointCnt;i++){
int currentMaxSquare = -1;
double currentMaxDist = 0;
int compareIdx = 0;
for(int j = compareStartIdx;j<pointCnt*2;j++){ compareIdx = j; if(compareIdx>=pointCnt){
compareIdx = j%pointCnt;
}
tempSquare = getSquare(pointSideList.get(i),pointSideList.get(i+1),pointSideList.get(compareIdx));
if(currentMaxSquare>tempSquare){
break;
}
else if(currentMaxSquare<tempSquare){ currentMaxSquare = tempSquare; currentMaxDist = Math.max(getDistance(pointSideList.get(i),pointSideList.get(compareIdx)),getDistance(pointSideList.get(i+1),pointSideList.get(compareIdx))); } else{ double tempDist = Math.max(getDistance(pointSideList.get(i),pointSideList.get(compareIdx)),getDistance(pointSideList.get(i+1),pointSideList.get(compareIdx))); if(tempDist>currentMaxDist){
currentMaxDist = tempDist;
currentMaxSquare = tempSquare;
break;
}
}
}
compareStartIdx = compareIdx+pointCnt-1;
maxDist = Math.max(maxDist,currentMaxDist);
}

System.out.println((int)maxDist);
}

private static double getDistance(int[] p1,int[] p2){
return Math.pow(p1[0]-p2[0],2)+Math.pow(p1[1]-p2[1],2);
}
//<p0,p1>,<p0,p2> private static int getSquare(int[] p0,int[] p1,int[] p2){
int[] v1 = new int[]{p1[0]-p0[0],p1[1]-p0[1]};
int[] v2 = new int[]{p2[0]-p0[0],p2[1]-p0[1]};
return Math.abs(v1[0]v2[1]-v1[1]v2[0]);
}

private static int sinZeroCompare(int[] p0,int[] p1,int[] p2){
int[] p01 = new int[]{p1[0]-p0[0],p1[1]-p0[1]};
int[] p12 = new int[]{p2[0]-p0[0],p2[1]-p0[1]};
return p01[0]p12[1]-p01[1]p12[0]>0?1:-1;
}
}