@瘋狂的方塊人

#include<bits/stdc++.h>

using namespace std;

int n,m,mn,mx,a[35];

bool c[35];

struct ben{

? ? double x,y;

}p[35],s[35],pp[35];

double check(ben a1,ben a2,ben b1,ben b2){

? ? return (a2.x-a1.x)*(b2.y-b1.y)-(b2.x-b1.x)*(a2.y-a1.y);

}

double d(ben p1,ben p2){

? ? return sqrt((p2.y-p1.y)*(p2.y-p1.y)+(p2.x-p1.x)*(p2.x-p1.x));

}

bool cmp(ben p1,ben p2){

? ? double tmp=check(pp[1],p1,pp[1],p2);

? ? if(tmp>0)?

return 1;

? ? if(tmp==0&&d(pp[0],p1)<d(pp[0],p2))?

return 1;

? ? return 0;

}

int __main(){

? ? int cnnt=1;

? ? for(int iii=1;iii<=n;iii++){

? ? ? ? if(c[iii])pp[cnnt++]=p[iii];

? ? }

? ? for(int i=2;i<=m;i++){

if(pp[i].y<pp[1].y){

? ? ? ? ? ? swap(pp[1].y,pp[i].y);

? ? ? ? ? ? swap(pp[1].x,pp[i].x);

? ? ? ? }

? ? }

? ? sort(pp+2,pp+1+m,cmp);

s[1]=pp[1];

? ? int cnt=1;

? ? for(int i=2;i<=m;i++){

? ? ? ? while(cnt>1&&check(s[cnt-1],s[cnt],s[cnt],pp[i])<=0)

? ? ? ? ? ? cnt--;

? ? ? ? cnt++;

? ? ? ? s[cnt]=pp[i];

? ? }

? ? s[cnt+1]=pp[1];

? ? double ans=0;

? ? for(int i=1;i<=cnt;i++){

ans+=d(s[i],s[i+1]);

? ? }

? ? return(int)(ans);

}

void dfs(int k){

? ? int i;

? ? if(k>m){

? ? ? ? int tmp=__main();

? ? ? ? if(a[k-1]==m){

? ? ? ? mx=tmp,mn=tmp;

}else{

mx=max(mx,tmp);

? ? ? ? mn=min(mn,tmp);

}

? ? ? ? return;

? ? }

? ? for(i=a[k-1]+1;i<=n;i++){

? ? ? ? c[i]=1;

? ? ? ? a[k]=i;

? ? ? ? dfs(k+1);

? ? ? ? a[k]=0;

? ? ? ? c[i]=0;

? ? }

}

int main(){

? ? scanf("%d%d",&n,&m);

? ? if(m==0){

? ? printf("0 0");

? ? exit(0);

}

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

? ? ? ? scanf("%lf%lf",&p[i].x,&p[i].y);

? ? }

? ? dfs(1);

? ? printf("%d %d",mn,mx);

? ? return 0;

}