[CodeForces]CodeForces 13D 几何 思维

时间：2023-03-09 18:41:46
[CodeForces]CodeForces 13D 几何 思维

　　大致题意：

　　　　给出N个红点和M个蓝点，问可以有多少个红点构成的三角形，其内部不含有蓝点

　　　假设我们现在枚举了一条线段（p[i],p[j]），我们可以记录线段下方满足(min（p[i].x,p[j].x）<x<=max（p[i].x,p[j].x） 的数量

　　　 时间复杂度为O（N*N*M）

　　　那么我们就可以枚举三角形O(1)判断三角形内有无红点。

　　

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #include<set>

 #include<map>

 #include<stack>

 #include<time.h>

 #include<cstdlib>

 #include<cmath>

 #include<list>

 using namespace std;

 #define MAXN 5000006

 #define eps 1e-9

 #define For(i,a,b) for(int i=a;i<=b;i++)

 #define Fore(i,a,b) for(int i=a;i>=b;i--)

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define mkp make_pair

 #define pb push_back

 #define cr clear()

 #define sz size()

 #define met(a,b) memset(a,b,sizeof(a))

 #define iossy ios::sync_with_stdio(false)

 #define fr freopen

 #define pi acos(-1.0)

 #define Vector Point

 #define fir first

 #define sec second

 #define it_s_too_hard main

 #define I_can_t_solve_it solve

 //const long long inf=1LL<<62;

 const int inf=1e9+;

 const int Mod=1e9+;

 typedef unsigned long long ull;

 typedef long long ll;

 typedef pair<int,int> pii;

 typedef pair<ll,ll> pll;

 typedef double ld;

 inline int dcmp(ld x){ if(fabs(x)<=eps) return ; return x<?-:;}

 inline int scan(){

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 inline ll scan(ll x){

     int f=;char ch=getchar();x=;

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 struct Point{

     int x,y;

     Point(int x=,int y=):x(x),y(y) {}

     Point operator - (const Point &a)const { return Point(x-a.x,y-a.y);}

     Point operator * (const ll &a)const{return Point(x*a,y*a);  }

     Point operator + (const Point &a)const{return Point(x+a.x,y+a.y);}

     bool operator == (const Point &a)const{ return dcmp(x-a.x)== && dcmp(y-a.y)==;}

     bool operator < (const Point &a)const{if(x==a.x) return y<a.y;return x<a.x;}

     void read(){scanf("%d%d",&x,&y);}

     void out(){cout<<x<<" "<<y<<endl;}

 };

 double Dot(Vector a,Vector b){

     return a.x*b.x+a.y*b.y;

 }

 double dis(Vector a){

     return sqrt(Dot(a,a));

 }

 ll Cross(Vector a,Vector b){

     return a.x*1LL*b.y-a.y*1LL*b.x;

 }

 bool chk(Point p1,Point p2,Point p3,Point p){

     return abs(Cross(p2-p,p1-p))+abs(Cross(p3-p,p2-p))+abs(Cross(p1-p,p3-p))==abs(Cross(p2-p1,p3-p1));

 }

 int n,m;

 Point p[],q[];

 int mp[][];

 void solve(){

     n=scan();m=scan();

     met(mp,);

     For(i,,n-) p[i].read();

     For(i,,m) q[i].read();

     sort(p,p+n);

     For(i,,n-){

         For(j,i+,n-){

             if(p[i].x==p[j].x) continue;

             For(k,,m){

                 if(q[k].x>p[i].x && q[k].x<=p[j].x && Cross(q[k]-p[j],p[i]-p[j])<) mp[i][j]++;

             }

         }

     }

     int ans=;

     For(i,,n-){

         For(j,i+,n-){

             For(k,j+,n-){

                 int c1=mp[i][j],c2=mp[j][k],c3=mp[i][k];

                 if(c1+c2==c3) ans++;

             }

         }

     }

     cout<<ans<<endl;

 }

 int it_s_too_hard(){

     int t=;

     For(i,,t){

         I_can_t_solve_it();

     }

     return ;

 }

蒻菜代码

相关文章