2017微软秋季校园招聘在线编程笔试

  1 //寻找M S的数量 2017微软秋季校园招聘在线编程笔试 hihocoder 1402 MS Recognition
  2 //看了讨论区写了一发
  3 //套一下思路：
  4 //有一个很简单的做法，一遍bfs找到一个端点，再一遍bfs找到另一个端点，然后把两个端点的中点和整个图形的重心比对一下，区分度非常大。具体来说就是比对一下端点中点到重心的距离，以及两个端点的距离的一半，二者相除，判断是否超过0.5即可。
  5 #include <bits/stdc++.h>
  6 using namespace std;
  7 #define LL long long
  8 typedef pair<int,int> pii;
  9 const int inf = 0x3f3f3f3f;
 10 const int N =1e5+10;
 11 #define clc(a,b) memset(a,b,sizeof(a))
 12 const double eps = 1e-8;
 13 const int MOD = 1e9+7;
 14 void fre() {freopen("in.txt","r",stdin);}
 15 void freout() {freopen("out.txt","w",stdout);}
 16 inline int read() {int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}return x*f;}
 17 
 18 int sgn(double x) {
 19     if(fabs(x) < eps)return 0;
 20     if(x < 0)return -1;
 21     else return 1;
 22 }
 23 
 24 struct Point {
 25     int x,y;
 26     Point() {}
 27     Point(int _x,int _y) {
 28         x = _x;
 29         y = _y;
 30     }
 31     Point operator -(const Point &b)const {
 32         return Point(x - b.x,y - b.y);
 33     }
 34     int operator ^(const Point &b)const {
 35         return x*b.y - y*b.x;
 36     }
 37     int operator *(const Point &b)const {
 38         return x*b.x + y*b.y;
 39     }
 40     friend int dis2(Point a) {
 41         return a.x*a.x+a.y*a.y;
 42     }
 43     friend bool operator<(const Point &a,const Point &b){
 44         if(fabs(a.y-b.y)<eps) return a.x<b.x;
 45         return a.y<b.y;
 46     }
 47 
 48 };
 49 
 50 double dis(Point a,Point b) {
 51     return sqrt((double)dis2(a-b));
 52 }
 53 
 54 int n,m;
 55 char g[510][510];
 56 bool vis[510][510];
 57 int dir[8][2]= {{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
 58 void dfs(int x,int y,int &lx,int &ly,int &rx,int &ry,Point &p1) {
 59     queue<Point>q;
 60     set<Point>s;
 61     s.insert(Point(x,y));
 62     q.push(Point(x,y));
 63     vis[x][y]=1;
 64     lx=x,ry=x,ly=y,ry=y;
 65     while(!q.empty()) {
 66         Point tem=q.front();
 67         q.pop();
 68         for(int i=0; i<8; i++) {
 69             int tx=tem.x+dir[i][0];
 70             int ty=tem.y+dir[i][1];
 71             if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&!s.count(Point(tx,ty))&&g[tx][ty]!='.') {
 72                 q.push(Point(tx,ty));
 73                 s.insert(Point(tx,ty));
 74                 vis[tx][ty]=1;
 75                 lx=min(lx,tx);
 76                 rx=max(rx,tx);
 77                 ly=min(ly,ty);
 78                 ry=max(ry,ty);
 79             }
 80         }
 81         p1=tem;
 82     }
 83 }
 84 
 85 int main() {
 86     scanf("%d%d",&n,&m);
 87     for(int i=1; i<=n; i++) {
 88         scanf("%s",g[i]+1);
 89     }
 90     int M=0,S=0;
 91     for(int i=1; i<=n; i++) {
 92         for(int j=1; j<=m; j++) {
 93             Point p1,p2,p3,p4;
 94             int lx,ly,rx,ry;
 95             if(vis[i][j]) continue;
 96             if(g[i][j]=='.') continue;
 97             lx=i,rx=i,ly=j,ry=j;
 98             dfs(i,j,lx,ly,rx,ry,p1);
 99             p3=Point((rx+lx)/2,(ry+ly)/2);
100             dfs(p1.x,p1.y,lx,ly,rx,ry,p2);
101             p4=Point((p1.x+p2.x)/2,(p1.y+p2.y)/2);
102             double len1=dis(p3,p4);
103             double len2=dis(p1,p2);
104             if(len1*2/len2<=0.5) S++;
105             else M++;
106         }
107     }
108     cout<<M<<" "<<S<<endl;
109     return 0;
110 }