首页 > 代码库 > 第四场B
第四场B
商汤科技近日推出的 SenseVideo 能够对视频监控中的对象进行识别与分析,包括行人检测等。在行人检测问题中,最重要的就是对行人移动的检测。由于往往是在视频监控数据中检测行人,我们将图像上的行人抽象为二维平面上若干个的点。那么,行人的移动就相当于二维平面上的变换。
在这道题中,我们将行人的移动过程抽象为 平移,有两个 移动参数:dx,dy.每次行人的移动过程会将行人对应的所有点全部平移,对于平移前的点 (x,y),平移后的坐标为 (x+dx,y+dy).?? 和 dyd_yd?y??。每次行人的移动过程会将行人对应的所有点全部平移,对于平移前的点 (x,y)(x, y)(x,y),平移后的坐标为 (x+dx,y+dy)(x + d_x, y + d_y)(x+d?x??,y+d?y??)。
我们现在已知一个行人对应着 n 个点,坐标分别为 (x1,y1),(x2,y2)…(xn,yn),平移后为(x1‘,y1‘)(x2‘,y2‘)(xn‘,yn‘).1??,y?1??),(x?2??,y?2??)…(x?n??,y?n??),平移后的坐标分别为 (x1′,y1′),(x2′,y2′)…(xn′,yn′)(x_1‘,y_1‘),(x_2‘,y_2‘)\ldots (x_n‘,y_n‘)(x?1?′??,y?1?′??),(x?2?′??,y?2?′??)…(x?n?′??,y?n?′??)。
很显然,通过平移前后的正确坐标,很容易算出行人的移动参数,但问题没有这么简单。由于行人实际的移动并不会完全按照我们预想的方式进行,因此,会有一部分平移后的坐标结果不正确,但可以确保 结果不正确的坐标数量严格不超过一半。
你现在作为商汤科技的实习生,接手了这个有趣的挑战:算出行人的移动参数。如果不存在一组合法的移动参数,则随意输出一组参数;如果有多种合法的移动参数,输出其中任意一组合法的即可。
输入格式
第一行输入一个整数 n(1≤n≤105)5??),表示行人抽象出的点数。
接下来 n 行,每行 4个 整数。前两个数表示平移前的坐标,后两个数表示平移后的坐标。
坐标范围在 -10^9?10^9?^9?? 到 10910^910?9?? 之间。
输出格式
一行两个整数,dx,dy表示人的移动参数。x?? 和 dyd_yd?y??,表示行人的移动参数。
样例输入
5 0 0 1 1 0 1 1 2 1 0 2 1 1 1 0 0 2 1 1 0
样例输出
1 1
思路:我们可以得到n组,x的移动参数,y的n的参数,用map存下,判断下就OK了
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 5 struct node{ 6 int x,y; 7 }a[100005]; 8 map<pair<int,int > ,int >b; 9 int main(){ 10 int n; 11 scanf("%d",&n); 12 int x1,x2,y1,y2; 13 for(int i=1;i<=n;i++){ 14 scanf("%d%d",&x1,&y1); 15 scanf("%d%d",&x2,&y2); 16 a[i].x=x2-x1; 17 a[i].y=y2-y1; 18 } 19 int m=n/2; 20 if(n%2==1) m++; 21 int xx=2,yy=2; 22 for(int i=1;i<=n;i++){ 23 b[make_pair(a[i].x,a[i].y)]++; 24 if( b[make_pair(a[i].x,a[i].y)]>=m){ 25 xx=a[i].x; 26 yy=a[i].y; 27 } 28 } 29 cout<<xx<<" "<<yy<<endl; 30 return 0; 31 }
第四场B