CSES 2195 - Convex Hull 解題心得( 題目 )
解題概念:幾何
解題方法:這題是凸包的模板題，這裡使用Andrew's algorithm分成上凸包跟下凸包處理，下方程式使用單調對列和外積判斷找到凸包，不過這裡注意因為題目給的限制，下方程式碼座標並沒有照順序排序，並且對於面積為0的凸包也沒有特判。
Java參考程式碼(有更好意見可留言於下方，謝謝!)
import java.io.*;
import java.util.*;
public class cses2195 {
public static int n,u_id=1,d_id=1,x1,x2,y1,y2;
public static int ret,r;
public static boolean neg;
public static P[] pt,up,dn;
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws Exception{
n=readint();
init();
for(int i=0;i<n;i++) {
pt[i]=new P(readint(),readint());
}
Sort();
up[0]=up[1]=pt[0];
dn[0]=dn[1]=pt[0];
Up_ConvexHull();
Down_ConvexHull();
bw.write((u_id+d_id-2)+"\n");//print ans
for(int i=u_id;i>0;i--) {
bw.write(up[i].x+" "+up[i].y+"\n");//print dots
}
for(int i=d_id-1;i>1;i--) {
bw.write(dn[i].x+" "+dn[i].y+"\n");
}
bw.flush();
}
public static void init() {
pt=new P[n];
up=new P[n+5];
dn=new P[n+5];
}
public static void Sort() {
Arrays.sort(pt,new Comparator<P>() {
public int compare(P f,P s) {
if(f.x==s.x) return f.y-s.y;
return f.x-s.x;
}
});
}
public static void Up_ConvexHull() throws Exception{
for(int i=1;i<n;i++) {
while(cross(up[u_id-1],up[u_id],pt[i])>0) {
u_id--;
}
up[++u_id]=pt[i];
}
}
public static void Down_ConvexHull() throws Exception{
for(int i=1;i<n;i++) {
while(cross(dn[d_id-1],dn[d_id],pt[i])<0) {
d_id--;
}
dn[++d_id]=pt[i];
}
}
public static long cross(P a,P b,P c) {
x1=b.x-a.x;
x2=c.x-b.x;
y1=b.y-a.y;
y2=c.y-b.y;
return (long)x1*y2-(long)x2*y1;
}
public static int readint() throws Exception {
neg=false;
ret=0;
r=br.read();
if(r=='-') {
neg=true;
r=br.read();
}
while(r>47&&r<58) {
ret*=10;
ret+=(r&15);
r=br.read();
}
if(neg)ret*=-1;
return ret;
}
}
class P{
int x,y;
P(int a,int b){
x=a;
y=b;
}
}
文章標籤
全站熱搜
