matrix_world_final

C http://acm.hust.edu.cn/vjudge/contest/view.action?cid=98613#problem/C

题意：输入16进制的n*m矩阵，其在二进制表示下有6种图中的哪几种。

解法：6种图黑点都是连通的，所以第一步先把黑的连通块标号，第二步6种图中白连通块的个数正好是0-5个，第二步每找到一个白块就找到它的边界，对应的黑块+1，最后每一个黑块中有多少白块就统计完了，按字典序输出即可。

 //#define debug

 //#define txtout

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<cctype>

 #include<ctime>

 #include<iostream>

 #include<algorithm>

 #include<vector>

 #include<queue>

 #include<stack>

 #include<map>

 #include<set>

 #define mt(a,b) memset(a,b,sizeof(a))

 using namespace std;

 typedef long long LL;

 const double eps=1e-;

 const double pi=acos(-1.0);

 const int inf=0x3f3f3f3f;

 const int M=2e2+;

 char a[M][M];

 char str[]="WAKJSD";

 bool black[M][M];

 int index_of_black;

 int id[M][M];

 int dx[]={,,,-};

 int dy[]={,-,,};

 int n,m;

 int sum[];

 int count_of_black[M*M];

 int id_of_black;

 vector<char> answer;

 int to_int(char c){

     if(isdigit(c)) return c-'';

     return c-'a'+;

 }

 void init_black(){

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

         int len=;

         for(int j=;j<m;j++){

             int value=to_int(a[i][j]);

             for(int k=;k>=;k--){

                 black[i][len++]=(value>>k)&;

             }

         }

     }

     m<<=;

 }

 void init_id(){

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

         for(int j=;j<m;j++){

             id[i][j]=;

         }

     }

 }

 void init_count_of_black(){

     for(int i=;i<=index_of_black;i++){

         count_of_black[i]=;

     }

 }

 bool inside(int x,int y){

     return x>=&&x<n&&y>=&&y<m;

 }

 void dfs_black(int x,int y,int Index){

     id[x][y]=Index;

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

         int tx=x+dx[i];

         int ty=y+dy[i];

         if(!inside(tx,ty)) continue;

         if(!black[tx][ty]) continue;

         if(id[tx][ty]) continue;

         dfs_black(tx,ty,Index);

     }

 }

 void solve_black(){

     index_of_black=;

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

         for(int j=;j<m;j++){

             if(!black[i][j]) continue;

             if(id[i][j]) continue;

             dfs_black(i,j,++index_of_black);

         }

     }

 }

 void dfs_white(int x,int y){

     id[x][y]=-;

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

         int tx=x+dx[i];

         int ty=y+dy[i];

         if(!inside(tx,ty)){

             id_of_black=;

             continue;

         }

         if(id[tx][ty]){

             if(id[tx][ty]>&&id_of_black==-){

                 id_of_black=id[tx][ty];

             }

             continue;

         }

         dfs_white(tx,ty);

     }

 }

 void solve_white(){

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

         for(int j=;j<m;j++){

             if(id[i][j]) continue;

             id_of_black=-;

             dfs_white(i,j);

             if(id_of_black==) continue;

             count_of_black[id_of_black]++;

         }

     }

 }

 void solve(){

     init_black();

     init_id();

     solve_black();

     init_count_of_black();

     solve_white();

     mt(sum,);

     for(int i=;i<=index_of_black;i++){

         sum[count_of_black[i]]++;

     }

     answer.clear();

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

         for(int j=;j<sum[i];j++){

             answer.push_back(str[i]);

         }

     }

     sort(answer.begin(),answer.end());

 }

 int main(){

     #ifdef txtout

     freopen("in.txt","r",stdin);

     freopen("out.txt","w",stdout);

     #endif

     int cas=;

     while(~scanf("%d%d",&n,&m),n|m){

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

             scanf("%s",a[i]);

         }

         solve();

         printf("Case %d: ",cas++);

         int len=answer.size();

         for(int i=;i<len;i++){

             putchar(answer[i]);

         }

         puts("");

     }

     return ;

 }

K http://acm.hust.edu.cn/vjudge/contest/view.action?cid=98613#problem/K

题意：求最小的能让任意多边形垂直下落通过的间距。

解法：先做凸包，求凸包的宽度即是答案。

 //#define debug

 //#define txtout

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<cctype>

 #include<ctime>

 #include<iostream>

 #include<algorithm>

 #include<vector>

 #include<queue>

 #include<stack>

 #include<map>

 #include<set>

 #define mt(a,b) memset(a,b,sizeof(a))

 using namespace std;

 typedef long long LL;

 const double eps=1e-;

 const double pi=acos(-1.0);

 const int inf=0x3f3f3f3f;

 const int M=1e2+;

 struct point {

     double x,y;

 } p[M],res[M];

 int n;

 char buffer[M];

 class Convex_Hull { ///凸包

     bool mult(point sp,point ep,point op) { ///>包括凸包边上的点,>=不包括。

         return (sp.x-op.x)*(ep.y-op.y)>=(ep.x-op.x)*(sp.y-op.y);

     }

     static bool cmp(const point &a,const point &b) { ///整数不需fabs，a.y==b.y。

         return a.y<b.y||(fabs(a.y-b.y)<eps&&a.x<b.x);

     }

 public:

     int Graham(int n,point p[],point res[]) { ///传入点的个数，点数组p[],凸包点存在res[],返回凸包点数.

         sort(p,p+n,cmp);

         if(n==) return ;

         res[]=p[];

         if(n==) return ;

         res[]=p[];

         if(n==) return ;

         res[]=p[];

         int top=;

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

             while(top&&mult(p[i],res[top],res[top-])) {

                 top--;

             }

             res[++top]=p[i];

         }

         int len=top;

         res[++top]=p[n-];

         for(int i=n-; i>=; i--) {

             while(top!=len&&mult(p[i],res[top],res[top-])) {

                 top--;

             }

             res[++top]=p[i];

         }

         return top;

     }

 } gx;

 class Convex_Hull_Wide{///凸包的宽

     double xmult(point p1,point p2,point p0) { ///计算向量叉积(P1-P0)x(P2-P0)

         return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);

     }

     double Square(double x) { ///平方

         return x*x;

     }

     double Distance(point a,point b) { ///平面两点距离

         return sqrt(Square(a.x-b.x)+Square(a.y-b.y));

     }

     double get(point a,point b,point c){

         return fabs(xmult(a,b,c));

     }

 public:

     double Rotate_Calipers_Wide(point p[],int n) {///传入凸包和点数

         double result=-;

         for(int i=,j=; i<n; i++) {

             while(get(p[j+],p[i+],p[i])>get(p[j],p[i+],p[i])){

                 j=(j+)%n;

             }

             double temp=get(p[j],p[i+],p[i])/Distance(p[i],p[i+]);

             if(result==-){

                 result=temp;

                 continue;

             }

             result=min(result,temp);

         }

         return result;

     }

 }ts;

 void round_up(double &x){

     sprintf(buffer,"%.6f",x);

     int len=strlen(buffer);

     for(int i=;i<len;i++){

         if(buffer[i]=='.'){

             if(buffer[i+]!=''){

                 buffer[i+]='';

             }

             break;

         }

     }

     sscanf(buffer,"%lf",&x);

 }

 double solve() {

     int len=gx.Graham(n,p,res);

     double result=ts.Rotate_Calipers_Wide(res,len);

     round_up(result);

     return result;

 }

 int main() {

 #ifdef txtout

     freopen("in.txt","r",stdin);

     freopen("out.txt","w",stdout);

 #endif

     int cas=;

     while(~scanf("%d",&n),n) {

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

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

         }

         printf("Case %d: %.2f\n",cas++,solve());

     }

     return ;

 }

end

巴特西

matrix_world_final_2011

最新文章

热门文章