竞赛讨论区 > 哪位大佬帮我看看这个代码为什么错了
头像
小乔(☆_☆)
发布于 2020-06-06 22:13
+ 关注

哪位大佬帮我看看这个代码为什么错了

#include<bits/stdc++.h>
#define mems(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int mod=1e9+7,N=305;
struct vec
{
    ll x,y;int id;
    vec(ll x=0,ll y=0):x(x),y(y){}
    bool operator==(const vec&o)const{return x==o.x&&y==o.y;}
    vec operator+(const vec&o)const{ return vec(x+o.x,y+o.y);}
    vec operator-(const vec&o)const{ return vec(x-o.x,y-o.y);}
    ll operator*(const vec&o)const{ return x*o.x+y*o.y;}
    ll operator^(const vec&o)const{ return x*o.y-y*o.x;}
    vec operator/(const ll&o)const{ return vec(x/o,y/o);}
    vec operator*(const ll&o)const{ return vec(x*o,y*o);}
    void sc(){scanf("%lld%lld",&x,&y);}
    ll len(){return x*x+y*y;}
}a[N],b[N],c[N],s,t;
int n,t1,t2,le[N],ri[N];
bool cmp1(vec a,vec b)
{
    return ((a-s)^(b-s))>0;
}
bool cmp2(vec a,vec b)
{
    return ((a-s)^(b-s))<0;
}
bool cmp3(vec a,vec b)
{
    return ((a-t)^(b-t))>0;
}
bool cmp4(vec a,vec b)
{
    return ((a-t)^(b-t))<0;
}
ll ans,res;
bool judge(vec a,vec b,vec c,vec d)
{
    ll t1=(a-b)^(b-c),t2=(a-b)^(b-d);
    return t1*t2<=0;
}
bool jiao(vec a,vec b,vec c,vec d)//线段相交
{
    return judge(a,b,c,d)&&judge(c,d,a,b);
}
void solve()
{
    t1=t2=0;
    for(int i=1;i<=n;i++)
    {
        if(c[i]==s||c[i]==t) continue;
        if(((t-s)^(c[i]-s))>0) a[++t1]=c[i],a[t1].id=t1;//线段t-s上的点
        else b[++t2]=c[i],b[t2].id=t2;//线段t-s下的点
    }
    ans+=t1*(t1-1)*(t1-2)/6;//线段上的三角形
    ans+=t2*(t2-1)*(t2-2)/6;//线段下的三角形
    sort(a+1,a+1+t1,cmp1);
    sort(b+1,b+1+t2,cmp1);
    //线段左边的三角形
    for(int i=1,j=1;i<=t1;i++)
    {
        while(j<=t2&&(jiao(s,t,a[i],b[j])||!jiao(s,t,a[i],b[j])&&((a[i]-b[j])^(s-b[j]))<0)) j++;
        ans+=(t2-j+1)*(i-1)+(t2-j+1)*(t2-j)/2;
        le[a[i].id]=t2-j+1;
    }
    sort(a+1,a+1+t1,cmp4);
    sort(b+1,b+1+t2,cmp4);
    //线段右边的三角形
    for(int i=1,j=1;i<=t1;i++)
    {
        while(j<=t2&&(jiao(s,t,a[i],b[j])||!jiao(s,t,a[i],b[j])&&((a[i]-b[j])^(s-b[j]))>0)) j++;
        ans+=(t2-j+1)*(i-1)+(t2-j+1)*(t2-j)/2;
        ri[a[i].id]=t2-j+1;
    }
    for(int i=1;i<=t1;i++) ans+=le[i]*ri[i];//包含线段,上一个点下两个点
    sort(a+1,a+1+t1,cmp2);
    sort(b+1,b+1+t2,cmp2);
    for(int i=1,j=1;i<=t2;i++)
    {
        while(j<=t1&&(jiao(s,t,a[j],b[i])||!jiao(s,t,a[j],b[i])&&((a[j]-b[i])^(s-b[i]))<0)) j++;
        le[b[i].id]=t1-j+1;
    }
    sort(a+1,a+1+t1,cmp3);
    sort(b+1,b+1+t2,cmp3);
    for(int i=1,j=1;i<=t2;i++)
    {
        while(j<=t1&&(jiao(s,t,a[j],b[i])||!jiao(s,t,a[j],b[i])&&((a[j]-b[i])^(s-b[i]))>0)) j++;
        ri[b[i].id]=t1-j+1;
    }
    for(int i=1;i<=t2;i++) ans+=le[i]*ri[i];//包含线段,上两个点下一个点
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) c[i].sc();
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)//枚举线段
    {
        s=c[i];t=c[j];
        solve();
    }
    printf("%lld\n",ans);
}
	

全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐