首页 > 代码库 > hdu--5128--计算几何<算不上.暴力模拟> && hdu--5131--初级cmp
hdu--5128--计算几何<算不上.暴力模拟> && hdu--5131--初级cmp
首先 给你N个点的坐标 你要找出其中的4个点来构造矩形
可以选择4个点 或者 一条对角线来进行构造
4个点 需要写个4层for 对角线只要2层for相比下 还是对角线比较好
虽然 我们会重复构造相同的矩形出来 但是没关系 题目数据很小的
接下来 就是矩形是否相交的判断了
注意一种特殊情况 矩阵 I 内含与 矩阵 J 或者是矩阵 j 内含i的含 就是得到外面的矩阵的面积
1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 5 int n , cnt; 6 const int size = 35; 7 struct data 8 { 9 int x , y;10 int minX , minY , maxX , maxY , area;11 }node[size],mat[size];12 bool vis[220][220];13 14 void getMat( )15 {16 for( int i = 0 ; i<n-1 ; i++ )17 {18 for( int j = i+1 ; j<n ; j++ )19 {20 if( node[i].x==node[j].x || node[i].y==node[j].y )21 continue;22 int minX = min( node[i].x , node[j].x );23 int maxX = max( node[i].x , node[j].x );24 int minY = min( node[i].y , node[j].y );25 int maxY = max( node[i].y , node[j].y );26 if( vis[minX][minY] && vis[minX][maxY] && vis[maxX][minY] && vis[maxX][maxY] )27 {28 mat[cnt].minX = minX , mat[cnt].minY = minY , mat[cnt].maxX = maxX , mat[cnt].maxY = maxY;29 mat[cnt++].area = (maxX-minX) * (maxY-minY);30 }31 }32 }33 }34 35 int solve( int i , int j )36 {37 //i与j相同38 if( mat[i].minX==mat[j].minX && mat[i].maxX==mat[j].maxX && mat[i].minY==mat[j].minY && mat[i].maxY==mat[j].maxY )39 return -1;40 //i包含了J41 if( mat[i].minX<mat[j].minX && mat[i].maxX>mat[j].maxX && mat[i].minY<mat[j].minY && mat[i].maxY>mat[j].maxY )42 return mat[i].area;43 //j包含了i44 if( mat[i].minX>mat[j].minX && mat[i].maxX<mat[j].maxX && mat[i].minY>mat[j].minY && mat[i].maxY<mat[j].maxY )45 return mat[j].area;46 //重叠的情况 以i或j为参考都可以 固定一个47 if( (mat[i].minX>=mat[j].minX&&mat[i].minX<=mat[j].maxX) || (mat[i].maxX>=mat[j].minX&&mat[i].maxX<=mat[j].maxX) )48 {49 if( (mat[i].minY>=mat[j].minY&&mat[i].minY<=mat[j].maxY) || (mat[i].maxY>=mat[j].minY&&mat[i].maxY<=mat[j].maxY) )50 {51 return -1;52 }53 } 54 if( (mat[j].minX>=mat[i].minX&&mat[j].minX<=mat[i].maxX) || (mat[j].maxX>=mat[i].minX&&mat[j].maxX<=mat[i].maxX) )55 {56 if( (mat[j].minY>=mat[i].minY&&mat[j].minY<=mat[i].maxY) || (mat[j].maxY>=mat[i].minY&&mat[j].maxY<=mat[i].maxY) )57 {58 return -1;59 }60 }61 return mat[i].area + mat[j].area;62 }63 64 int main()65 {66 int ans;67 while( cin >> n && n )68 {69 memset( vis , false , sizeof(vis) );70 cnt = 0;71 for( int i = 0 ; i<n ; i++ )72 {73 cin >> node[i].x >> node[i].y;74 vis[ node[i].x ][ node[i].y ] = true;75 }76 getMat( );77 ans = -1;78 for( int i = 0 ; i<cnt-1 ; i++ )79 {80 for( int j = i+1 ; j<cnt ; j++ )81 {82 ans = max( ans , solve(i,j) );83 }84 }85 if( ans==-1 )86 cout << "imp" << endl;87 else88 cout << ans << endl;89 }90 return 0;91 }
虽然写麻烦了=_= 但毕竟容易接受 就是判断出所有的不同情况来
懒得再开一篇了 将5131也放一起吧
它相比上题 难度差不多 但是容易写啊 没什么要注意的。。
1 #include <iostream> 2 #include <algorithm> 3 #include <string> 4 #include <map> 5 using namespace std; 6 7 int n; 8 const int size = 220; 9 map<string,int>mp;10 struct data11 {12 string name;13 int num;14 }node[size];15 16 bool cmp( const data p , const data q )17 {18 if( p.num == q.num )19 {20 return p.name < q.name;21 }22 return p.num > q.num;23 }24 25 void work( )26 {27 for( int i = 0 ; i<n ; i++ )28 {29 cout << node[i].name << " " << node[i].num << endl;30 mp[ node[i].name ] = i;31 }32 }33 34 int main()35 {36 cin.sync_with_stdio(false);37 int m , index , temp;38 char str[60];39 while( cin >> n && n )40 {41 mp.clear();42 for( int i = 0 ; i<n ; i++ )43 {44 cin >> node[i].name >> node[i].num;45 }46 sort( node , node+n , cmp );47 cin >> m;48 work( );49 while( m-- )50 {51 cin >> str;52 temp = mp[str];53 index = temp;54 while( index>=1 )55 {56 if( node[index-1].num == node[index].num )57 {58 -- index;59 }60 else61 break;62 }63 cout << index+1;64 index = max( 1 , temp-index+1 );65 if( index>1 )66 cout << " " << index;67 cout << endl;68 }69 }70 return 0;71 }
hdu--5128--计算几何<算不上.暴力模拟> && hdu--5131--初级cmp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。