题解 P4623 【[COCI2012-2013#6] BUREK】

冰凉的水 · 2018-10-24 08:11:19 · 题解

• 本人的思路清奇诡异，机房考试是数据加强版（-1e9～1e9），所以需要离散化，此题可以不用。不过，我的思路是排序+差分（机房数据大，空间开不下）。

• 首先，约束条件：直线从三角形中间穿过。

• 因为，只有平行于坐标轴的直线，所以将x，y轴拆开看，就可以看成端点和树轴（想象力不好的同学可以手绘 模拟 %ni一下）。

• 所以穿过三角形的直线符合xE(min(x1,x2,x3),max(x1,x2,x3)),yE(min(y1,y2,y3),max(y1,y2,y3) )。(因为不会打属于符号，用E代替(T_T))

• 将所有左端点（标记一下），右端点，查询x（标记一下）记录在一起，y另外记录在一起。

• 接下来，就是差分的思想，我们在左端点+1的位置给贡献加一（注意是左端点加一，因为经过端点不算穿过），在右端点的位置减一，那么，从前面累加起的值就是这个点的答案（不就是前缀和嘛，不理解的同学好好想想 ）。

• 最后，我们存下查询的时间戳（chuo，好像蛮多人以为是截，的确蛮像的），保存在ans数组里输出统计的答案。

• AC代码（保持了数据加强后的空间大小，可自己计算更改）：

• #include<bits/stdc++.h>
  using namespace std;
  int read()//快读还需要解释吗？
  {
  int x=0,fg=1;char ch=getchar();
  while(ch<'0'||ch>'9'){if(ch=='-')fg*=-1;ch=getchar();}
  while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
  return x*fg;
  }
  const int N=1000010;
  struct node{
  int val,id;  //  val存端点位置,id存访问时间戳
  int dir,left;//  dir是查询标记，left是左端点标记
  }x[N],y[N];      //  x，y分开处理
  bool cmp(node c,node d)// 将端点优先于查询，小端点优于大端点
  {
  return c.val==d.val?c.dir<d.dir:c.val<d.val;
  }
  int n,m,totx,toty,ans[N];
  int main()
  {
  //freopen("burek.in","r",stdin);
  //freopen("burek.out","w",stdout);
  n=read();
  for(int i=1;i<=n;++i)//读入三角形
  {
      int x1=read(),y1=read(),x2=read(),y2=read(),x3=read(),y3=read();
      x[++totx].val=min(x1,min(x2,x3))+1;x[totx].left=1;
      //直接在左端点加入时就+1
      x[++totx].val=max(x1,max(x2,x3));
      y[++toty].val=min(y1,min(y2,y3))+1;y[toty].left=1;
      y[++toty].val=max(y1,max(y2,y3));
  }
  m=read();
  for(int i=1;i<=m;i++)//读入查询
  {
      char ch[5];cin>>ch;
      if(ch[0]=='x')
      {
          cin>>ch;
          x[++totx].val=read();
          x[totx].id=i;
          x[totx].dir=1;
      }
      else if(ch[0]=='y')
      {
          cin>>ch;
          y[++toty].val=read();
          y[toty].id=i;
          y[toty].dir=1;
      }
  }
  sort(x+1,x+1+totx,cmp);//排序
  sort(y+1,y+1+toty,cmp);
  int sum=0;            //前缀和统计，本人较懒不想开数组
  for(int i=1;i<=totx;i++)
  {
      if(x[i].dir)ans[x[i].id]=sum;//对于查询记录答案
      else if(x[i].left)++sum;//左端点+1的位置+1
      else --sum;          //右端点-1
  }
  sum=0;  //记得清零
  for(int i=1;i<=toty;i++)//同上
  {
      if(y[i].dir)ans[y[i].id]=sum;
      else if(y[i].left)++sum;
      else --sum;
  }
  for(int i=1;i<=m;i++)//输出答案
  printf("%d\n",ans[i]);
  return 0;
  }

• 以上就是全部内容，路过的大佬是不是秒懂呀。