网站建设 知乎,网站建设配置文件无法粘贴,网络广告公司,做好我局门户网站建设工作这道题。。太特么多细节了。。 题意#xff1a;在平面直角坐标系中给你N个点#xff0c;stan和ollie玩一个游戏#xff0c;首先stan在竖直方向上画一条直线#xff0c;该直线必须要过其中的某个点#xff0c;然后ollie在水平方向上画一条直线#xff0c;该直线的要求是要…这道题。。太特么多细节了。。 题意在平面直角坐标系中给你N个点stan和ollie玩一个游戏首先stan在竖直方向上画一条直线该直线必须要过其中的某个点然后ollie在水平方向上画一条直线该直线的要求是要经过一个stan之前画过的点。 这时候平面就被分割成了四块两个人这时候会有一个得分stan的得分是平面上第1、3象限内的点的个数ollie的得分是平面上第2、4象限内的点的个数在统计的时候在所画线上的点都不计算在内。求最终stan使得自己的最差得分最高并且输出此时ollie的得分。 题解 我们可以枚举哪颗星星是中心点然后就可以知道他们所确定的直线。 线上可以维护四个值updownleftright分别表示线上四个方位有多少颗星星。 然后我们只要求BL,就可以知道其它 TL横坐标比x小的星星总数-BL-left TRy坐标比x大的星星总数-TL-up BRy坐标比x小的星星总数-BL-down 各种细节 1 #includecstdio2 #includecstdlib3 #includecstring4 #includeiostream5 #includealgorithm6 using namespace std;7 8 const int N200010,INF(int)1e9100;9 int n,pl,mx,c[N],cntx[N],cnty[N],sumx[N],sumy[N],sx[N][2],sy[N][2],u[N],d[N],l[N],r[N],a1[N],a2[N];10 bool num[N];11 struct node{12 int x,y;13 }a[N];14 struct nd{15 int d,id,tmp;16 }p[2*N];17 18 bool cmp_num(int x,int y){return xy;}19 bool cmp_d(nd x,nd y){return x.dy.d;}20 bool cmp_a(node x,node y)21 {22 if(x.xy.x) return x.yy.y;23 return x.xy.x;24 }25 int maxx(int x,int y){return xy ? x:y;}26 27 void clear()28 {29 memset(cntx,0,sizeof(cntx));30 memset(cnty,0,sizeof(cnty));31 memset(sumx,0,sizeof(sumx));32 memset(sumy,0,sizeof(sumy));33 memset(c,0,sizeof(c));34 memset(a1,63,sizeof(a1));35 memset(a2,-1,sizeof(a2));36 }37 38 void add(int x)39 {40 for(int ix;imx;i(i(-i))) c[i];41 }42 int getsum(int x)43 {44 int ans0;45 for(int ix;i1;i-(i(-i))) ansc[i];46 return ans;47 }48 49 int main()50 {51 freopen(a.in,r,stdin);52 // freopen(me.out,w,stdout);53 while(1)54 {55 scanf(%d,n);56 if(n0) break;57 pl0;clear();58 for(int i1;in;i)59 {60 scanf(%d%d,a[i].x,a[i].y);61 p[pl].da[i].x;p[pl].idi;p[pl].tmp0;62 p[pl].da[i].y;p[pl].idi;p[pl].tmp1;63 }64 sort(p1,p1pl,cmp_d);65 mx0;p[0].dINF;66 for(int i1;ipl;i)67 {68 if(p[i].d!p[i-1].d) mx;69 if(p[i].tmp0) a[p[i].id].xmx;70 else a[p[i].id].ymx;71 }72 73 sort(a1,a1n,cmp_a);74 // for(int i1;in;i) 75 // printf(%d %d\n,a[i].x,a[i].y);76 for(int i1;in;i)77 {78 d[i]cntx[a[i].x];cntx[a[i].x];79 l[i]cnty[a[i].y];cnty[a[i].y];80 }81 // for(int i1;imx;i) 82 // printf(i %d %d %d\n,i,cntx[i],cnty[i]);83 for(int i1;in;i)84 {85 u[i]cntx[a[i].x]-d[i]-1;86 r[i]cnty[a[i].y]-l[i]-1;87 }88 for(int i1;imx;i) 89 {90 sumx[i]sumx[i-1]cntx[i];91 sumy[i]sumy[i-1]cnty[i];92 }93 for(int i1;in;i)94 {95 int xa[i].x,ya[i].y;96 sx[i][0]sumx[x-1];97 sx[i][1]sumx[mx]-sumx[x];98 sy[i][0]sumy[y-1];99 sy[i][1]sumy[mx]-sumy[y];
100 }
101 // for(int i1;in;i)
102 // {
103 // printf(%d sx0 %d sx1 %d sy0 %d sy1 %d d %d u %d l %d r %d\n,i,sx[i][0],sx[i][1],sy[i][0],sy[i][1],d[i],u[i],l[i],r[i]);
104 // }
105 for(int i1;in;i)
106 {
107 int xa[i].x,ya[i].y;
108 int BLgetsum(a[i].y-1)-d[i];
109 int TLsx[i][0]-BL-l[i];
110 int TRsy[i][1]-TL-u[i];
111 int BRsy[i][0]-BL-d[i];
112 add(y);
113 if(TRBLa1[x]) a1[x]TRBL,a2[x]TLBR;
114 else if(TRBLa1[x]) a2[x]maxx(a2[x],TLBR);
115 // printf(%d BL %d BR %d TR %d TL %d\n,i,BL,BR,TR,TL);
116 }
117 int ans0,nl0;;
118 for(int i1;imx;i)
119 {
120 if(a1[i]INF) ansmaxx(ans,a1[i]);
121 }
122 printf(Stan: %d; Ollie:,ans);
123 memset(num,0,sizeof(num));
124 for(int i0;in;i)
125 if(a1[i]ans) num[a2[i]]1;
126 for(int i0;in;i)
127 if(num[i]) printf( %d,i);
128 printf(;\n);
129 }
130 return 0;
131 } 转载于:https://www.cnblogs.com/KonjakJuruo/p/6040504.html
