2016多校训练Contest5：1004 How Many Triangles

正文索引 [隐藏]

题目翻译
题解
代码

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5784

题目翻译

屏幕上有 N 个点，求问这些点能组成多少个三角形。 ( 3≤n≤2000 && 0≤xi,yi≤1e9 )

题解

需要知道一个奇怪的结论，三角形个数 = ( 锐角数量 – 钝角&直角数量 × 2 ) ÷ 3
于是，问题转化为了如何求平面内的钝角/直角/锐角。
首先，我们枚举每个角的顶点，通过这个顶点，把其他店都变成向量，那么现在的所有角就是任意两个向量的夹角了。然后，我们再枚举两个向量中的第一个向量，通过计算的二个向量的个数，来得到钝角/直角/锐角的数量。通过把这些向量极角排序，我们发现可以有单调性，于是复杂度就有了保证。 O(n^2logn)

代码

/*
  Author : WNJXYK
  Problem : 1004
  Blog : http://wnjxyk.cn
  Date : 2016
*/
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int Maxn=2000;
struct PoiNode{
    LL x,y;
};
struct VecNode{
    LL x,y;
    VecNode(){}
    VecNode(PoiNode a,PoiNode b){
        x=b.x-a.x;
        y=b.y-a.y;
    }
};
LL dot(VecNode a,VecNode b){
    return a.x*b.x+a.y*b.y;
}
LL det(VecNode a,VecNode b){
    return a.x*b.y-a.y*b.x;
}
LL dis(VecNode a){
    return a.x*a.x + a.y*a.y;
}
inline bool cmp(VecNode a,VecNode b){
    //极角序 4 3 1 2
    if (a.y*b.y<=0){ //不在相同上下片区
        if (a.y>0 || b.y>0) return a.y<b.y; //优先去下半区
        if (a.y==0 && b.y==0) return a.x<b.x; //在X轴上优先去负半轴
    }
    return det(a,b)>0;//顺时针排序
}
PoiNode poi[Maxn+5];
VecNode vec[Maxn*2+5];
int cnt;
int n;
inline void solve(){
    for (int i=1;i<=n;i++) scanf("%I64d%I64d",&poi[i].x,&poi[i].y);
    LL rj=0,zdj=0;
    for (int core=1;core<=n;core++){
        cnt=0;
        for (int j=1;j<=n;j++)
            if (core!=j)
                vec[++cnt]=VecNode(poi[core],poi[j]);
        sort(vec+1,vec+cnt+1,cmp);
        //cout<<"Sort"<<endl;
        //for (int i=1;i<=cnt;i++) printf("%I64d %I64d\n",vec[i].x,vec[i].y);
        for (int i=1;i<=cnt;i++) vec[i+cnt]=vec[i];
        for (int i=1,j=1,k=1,r=1;i<=cnt;i++){
            while(j<=i+cnt-1 && det(vec[i],vec[j])==0 && dot(vec[i],vec[j])>0) j++;
            k=max(k,j);
            while(k<=i+cnt-1 && det(vec[i],vec[k])>0 && dot(vec[i],vec[k])>0) k++;
            r=max(r,k);
            while(r<=i+cnt-1 && det(vec[i],vec[r])>0) r++;
            rj += (LL)k-(LL)j;
            zdj += (LL)r-(LL)k;
        }
    }
    //printf("%I64d %I64d\n",rj,zdj);
    printf("%I64d\n",(rj-zdj*(LL)2)/(LL)3);
}
int main(){
    //freopen("in.txt","r",stdin);
    while(scanf("%d",&n)!=EOF) solve();
    return 0;
}

Author : WNJXYK

Problem : 1004

Blog : http://wnjxyk.cn

Date : 2016

#include <bits/stdc++.h>

#define LL long long

using namespace std;

const int Maxn=2000;

struct PoiNode{

LL x,y;

};

struct VecNode{

LL x,y;

VecNode(){}

VecNode(PoiNode a,PoiNode b){

x=b.x-a.x;

y=b.y-a.y;

}

};

LL dot(VecNode a,VecNode b){

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

}

LL det(VecNode a,VecNode b){

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

}

LL dis(VecNode a){

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

}

inline bool cmp(VecNode a,VecNode b){

//极角序 4 3 1 2

if (a.y*b.y<=0){ //不在相同上下片区

if (a.y>0 || b.y>0) return a.y<b.y; //优先去下半区

if (a.y==0 && b.y==0) return a.x<b.x; //在X轴上优先去负半轴

}

return det(a,b)>0;//顺时针排序

}

PoiNode poi[Maxn+5];

VecNode vec[Maxn*2+5];

int cnt;

int n;

inline void solve(){

for (int i=1;i<=n;i++) scanf("%I64d%I64d",&poi[i].x,&poi[i].y);

LL rj=0,zdj=0;

for (int core=1;core<=n;core++){

cnt=0;

for (int j=1;j<=n;j++)

if (core!=j)

vec[++cnt]=VecNode(poi[core],poi[j]);

sort(vec+1,vec+cnt+1,cmp);

//cout<<"Sort"<<endl;

//for (int i=1;i<=cnt;i++) printf("%I64d %I64d\n",vec[i].x,vec[i].y);

for (int i=1;i<=cnt;i++) vec[i+cnt]=vec[i];

for (int i=1,j=1,k=1,r=1;i<=cnt;i++){

while(j<=i+cnt-1 && det(vec[i],vec[j])==0 && dot(vec[i],vec[j])>0) j++;

k=max(k,j);

while(k<=i+cnt-1 && det(vec[i],vec[k])>0 && dot(vec[i],vec[k])>0) k++;

r=max(r,k);

while(r<=i+cnt-1 && det(vec[i],vec[r])>0) r++;

rj += (LL)k-(LL)j;

zdj += (LL)r-(LL)k;

}

//printf("%I64d %I64d\n",rj,zdj);

printf("%I64d\n",(rj-zdj*(LL)2)/(LL)3);

}

int main(){

//freopen("in.txt","r",stdin);

while(scanf("%d",&n)!=EOF) solve();

return 0;

}

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

WNJXYKの博客

喂你脚下有坑