Chieh's Blog

Because Of Coding

R308 DIV2 D. Vanya and Triangles

Chieh posted @ 2015年6月19日 15:29 in codeforces , 348 阅读

飞机票：http://codeforces.com/contest/552/problem/D

题意：给你n个点，两两相连，一共有多少个三角形是已给出n个点中三个点组成的

分析：这题的话O（n3）能过，我不知道出题人是什么意思，，，我的话是n*40000.最多也就O(10*n*n)的复杂度，跑了173ms。直接进入正题：此题可以用计数容斥来做，具体就是对与每个点i 对(i+1~n)进行枚举。(1<=i<=n)具体的做法是：假设当前的点是i，枚举(i+1~n)和i的斜率，并把斜率存入到数组中，因为最大的yj-yi=200 xj-xi=200，所以存入到200*200的数组中就可以了但是这里我们必须把(yj-yi)和(xj-xi)的最大公约数求出来，假设除了最大公约数后分别为p和q，因为这样才可以知道斜率为p/q的点关于i有多少个。这里的话，我们可以预处理下1~200每对的最大公约数，这样就是O（1）的时间求最大公约数了。而且我是用了两个数组，一个存斜率是正数，一个存斜率是负数，而且还得存p=0或q=0的情况。最后就是对三角形的个数进行统计，假设斜率为k的点有有l个，除了l个点和i点后有r个点，则三角形个数就是l*r，因为l上选一个点，i一个点，r上一个点，计算完后，需要把重复的除掉，因为对于两个点a和b，我们计算了a到b和b到a的，所以最后除以2就可以了，然后加到总数上去最后啪啪啪，就可以AC了。

?
G++ code
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <vector>
#include <queue>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
int x1[201][201];
int y11[201][201];
int G[201][201];
const int maxn=2*1234;
struct he
{
    int x,y;
} Sky[maxn];
int n;
void init()
{
    for(int i=1; i<=n; i++)scanf("%d%d",&Sky[i].x,&Sky[i].y);
}
void play()
{
    LL ans=0;
    for(int i=1; i<=n; i++)
    {
        memset(x1,0,sizeof(x1));
        memset(y11,0,sizeof(y11));
        int l=0;
        int r=0;
        for(int j=i+1; j<=n; j++)
        {
            int q=Sky[i].y-Sky[j].y;
            int p=Sky[i].x-Sky[j].x;
 
            if(p==0)
            {
                l++;
            }
            else if(q==0)
            {
                r++;
            }
            else
            {
                int nn=G[abs(q)][abs(p)];
                q/=nn;
                p/=nn;
                if(q>0&&p>0)
                {
                    x1[q][p]++;
                }
                else if(q<0&&p<0)
                {
                    x1[-q][-p]++;
                }
                else
                {
                    y11[abs(q)][abs(p)]++;
                }
            }
 
        }
        LL sum=0;
        int sk=n-i;
        if(l!=0)
        {
            sum+=(sk-l)*l;
        }
        if(r!=0)
        {
            sum+=(sk-r)*r;
        }
        for(int j=1; j<=200; j++)
        {
            for(int k=1; k<=200; k++)
            {
                int p=x1[j][k];
                int q=y11[j][k];
                if(p!=0)
                {
                    sum+=(sk-p)*p;
                }
                if(q!=0)
                {
                    sum+=(sk-q)*q;
                }
            }
        }
        sum/=2;
        ans+=sum;
    }
    printf("%I64d\n",ans);
}
int GCD(int a,int b)
{
    if(a<b)swap(a,b);
    if(a%b!=0)
    {
        return GCD(b,a%b);
    }
    return b;
}
int main()
{
    for(int i=1; i<=200; i++)
    {
        for(int j=1; j<=200; j++)
        {
            G[i][j]=GCD(i,j);
        }
    }
 
    while(scanf("%d",&n)!=EOF)
    {
        init();
        play();
    }
//    cout << "Hello world!" << endl;
    return 0;
}
Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter