<output id="qn6qe"></output>

    1. <output id="qn6qe"><tt id="qn6qe"></tt></output>
    2. <strike id="qn6qe"></strike>

      亚洲 日本 欧洲 欧美 视频,日韩中文字幕有码av,一本一道av中文字幕无码,国产线播放免费人成视频播放,人妻少妇偷人无码视频,日夜啪啪一区二区三区,国产尤物精品自在拍视频首页,久热这里只有精品12

      Codeforces 70D. Professor's task

      題目鏈接:D - Professor's task

      題目大意:初始給三個點,之后要求實現兩種操作:加點;判斷給定點是否在凸包內部。

      動態凸包板子題,留檔怕忘了,參考 http://www.rzrgm.cn/enzymii/p/8413480.html

      #include<bits/stdc++.h>
      using namespace std;
      #define N 100010
      #define LL long long
      struct Point
      {
          int x,y;
          void read(){scanf("%d%d",&x,&y),x*=3,y*=3;}
          Point operator +(const Point &t)const{return {x+t.x,y+t.y};}
          Point operator -(const Point &t)const{return {x-t.x,y-t.y};}
          LL operator *(const Point &t)const{return 1ll*x*t.y-1ll*y*t.x;}
          Point operator *(const int &k)const{return {x*k,y*k};}
          Point operator /(const int &k)const{return {x/k,y/k};}
          bool operator ==(const Point &t)const{return x==t.x && y==t.y;}
          LL norm(){return 1ll*x*x+1ll*y*y;}
      }G,A,B,C;
      bool operator <(const Point &A,const Point &B)
      {
          Point p1=A-G,p2=B-G;
          if(p1.x==0 && p1.y==0)return true;
          if(p2.x==0 && p2.y==0)return false;
          if(1ll*p1.y*p2.y<0)return p1.y>p2.y;
          LL Cr=p1*p2;
          if(Cr)return Cr>0;
          if(p1.y==0 && 1ll*p1.x*p2.x<0)return p1.x>p2.x;
          return p1.norm()<p2.norm();
      }
      set<Point>s;
      typedef set<Point>::iterator cdx;
      cdx pre(cdx it)
      {
          if(it==s.begin())it=s.end();
          it--;return it;
      }
      cdx nxt(cdx it)
      {
          ++it;
          if(it==s.end())it=s.begin();
          return it;
      }
      bool In(Point P)
      {
          auto it=s.lower_bound(P);
          if(it==s.end())it=s.begin();
          LL Cr=(P-*pre(it))*(*it-P);
          if(Cr==0)return (P-*pre(it)).norm()<=(*it-*pre(it)).norm();
          return Cr<0;
      }
      void Ins(Point P)
      {
          if(In(P))return;
          auto it=s.lower_bound(P);
          if(it==s.end())it=s.begin();
          s.insert(P);
          while(s.size()>3 && (*it-P)*(*nxt(it)-*it)<=0)
              s.erase(it),it=nxt(s.find(P));
          it=pre(s.find(P));
          while(s.size()>3 && (*pre(it)-*it)*(*it-P)<=0)
              s.erase(it),it=pre(s.find(P));
      }
      int q,o;
      int main()
      {
          scanf("%d",&q);
          q--,scanf("%d",&o),A.read();
          q--,scanf("%d",&o),B.read();
          q--,scanf("%d",&o),C.read();
          G=(A+B+C)/3;
          s.insert(A),s.insert(B),s.insert(C);
          while(q--){
              scanf("%d",&o),A.read();
              if(o==2)printf("%s\n",In(A)?"YES":"NO");
              else Ins(A);
          }
      }

       

      posted @ 2023-03-22 23:30  DeaphetS  閱讀(43)  評論(0)    收藏  舉報
      主站蜘蛛池模板: 一个人免费观看WWW在线视频| 99国产精品欧美一区二区三区| 亚洲熟妇自偷自拍另类| 亚洲性日韩精品一区二区| 亚洲国产超清无码专区| 国产亚洲综合欧美视频| 日本一高清二区视频久二区| 国产福利在线观看免费第一福利| 日韩精品无码去免费专区| 中文国产人精品久久蜜桃| 亚洲精品久久久久久下一站| 承德县| 国产国产午夜福利视频| 美欧日韩一区二区三区视频| 人人入人人爱| 国产精品无码a∨麻豆| 最新国产精品好看的精品| 精品福利视频一区二区三区| 欧洲无码一区二区三区在线观看| 国产日韩一区二区三区在线观看| 国产精品国产精品国产精品| 不卡一区二区国产精品| 亚洲成色精品一二三区| 综合久青草视频在线观看| 午夜激情福利一区二区| 亚洲精品日韩中文字幕| 亚洲人成电影在线天堂色| 精品免费看国产一区二区| 东方av四虎在线观看| 一区二区三区精品不卡| 国产精品国产高清国产av| 一道本AV免费不卡播放| 免费看美女被靠到爽的视频| 国产av一区二区三区精品| 国产精品自拍午夜福利| 久久99精品久久水蜜桃| 中文字幕色偷偷人妻久久| 国产精品午夜福利免费看| 国产精品色哟哟成人av| 92精品国产自产在线观看481页| 国产精品亚洲二区在线看|