2 条题解

  • 0
    @ 2025-10-8 16:58:07
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=1e5+10;
    const double Pi=acos(-1.0);
    const double eps=1e-10;
    struct point
    {
        int x,y;double k;
        bool operator <(const point &b) const{return k<b.k;}
    }p[N<<1];
    
    int main()
    {
        int n; scanf("%d",&n);if(n<=2){puts("0");return 0;}
        for(int i=1;i<=n;++i)
        {
            scanf("%d%d",&p[i].x,&p[i].y);
            p[i].k=atan2(p[i].y,p[i].x);
        }
        sort(p+1,p+1+n);
    
        ll ans=1ll*n*(n-1)*(n-2)/6;
        
        for(int i=n+1;i<=(n<<1);++i)p[i]=p[i-n],p[i].k+=2*Pi;
        for( int i=1,l,r=1;i<=n;++i)
        {
            l=i+1;
            while(p[r+1].k+eps<p[i].k+Pi)++r;
            ans-=1ll*(r-l+1)*(r-l)/2;
        }
        printf("%lld\n",ans);
        return 0;
    }
    
    • 0
      @ 2025-10-8 16:58:00
      #include <bits/stdc++.h>
      using namespace std;
      typedef long long ll;
      const int N=1e5+10;
      const double Pi=acos(-1.0);
      const double eps=1e-10;
      struct point
      {
          int x,y;double k;
          bool operator <(const point &b) const{return k<b.k;}
      }p[N<<1];
      
      int main()
      {
          int n; scanf("%d",&n);if(n<=2){puts("0");return 0;}
          for(int i=1;i<=n;++i)
          {
              scanf("%d%d",&p[i].x,&p[i].y);
              p[i].k=atan2(p[i].y,p[i].x);
          }
          sort(p+1,p+1+n);
      
          ll ans=1ll*n*(n-1)*(n-2)/6;
          
          for(int i=n+1;i<=n<<1;++i)p[i]=p[i-n],p[i].k+=2*Pi;
          for( int i=1,l,r=1;i<=n;++i)
          {
              l=i+1;
              while(p[r+1].k+eps<p[i].k+Pi)++r;
              ans-=1ll*(r-l+1)*(r-l)/2;
          }
          printf("%lld\n",ans);
          return 0;
      }
      • 1

      *【容斥原理】统计包含原点的三角形[USACO10OPEN] Triangle Counting G

      信息

      ID
      1620
      时间
      1000ms
      内存
      128MiB
      难度
      9
      标签
      递交数
      10
      已通过
      7
      上传者