2020牛客寒假算法基礎訓練營2

文章目錄

• • • 數三角
    • 做計數

數三角

• 題意

給出坐标，求最多能組成多少個鈍角三角形。

• 思路

鈍角三角形兩邊平方和大于第三邊平方，a^2 + b^2 > c^2。但比賽的時候忘記判斷一下能不能構成三角形了。。

• 代碼

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
 
using namespace std;
 
long long x[510],y[510];
long long t[5];
 
int main(){
    int n;
    long long ans = 0;
    long long x1,y1,x2,y2,x3,y3;
    double t1,t2,t3;
    cin >> n;
    for(int i = 1;i <= n;i++) {
        scanf("%lld%lld",&x[i],&y[i]);
    }
    for(int i = 1;i <= n - 2;i++) {
        for(int j = i + 1;j <= n - 1;j++) {
            for(int k = j + 1;k <= n;k++) {
                x1 = abs(x[i] - x[j]);
                y1 = abs(y[i] - y[j]);
                x2 = abs(x[i] - x[k]);
                y2 = abs(y[i] - y[k]);
                x3 = abs(x[j] - x[k]);
                y3 = abs(y[j] - y[k]);
                t[0] = x1 * x1 + y1 * y1;
                t[1] = x2 * x2 + y2 * y2;
                t[2] = x3 * x3 + y3 * y3;
                sort(t,t + 3);
                t1 = sqrt(t[0]);
                t2 = sqrt(t[1]);
                t3 = sqrt(t[2]);
                if(t[0] + t[1] < t[2] && t1 + t2 > t3) {
                    ans++;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}
           

做計數

• 題意

求n範圍内構成i^(1/2) + j^(1/2) = k^(1/2)的三元組（i，j，k）的個數。

• 思路

找平方數和平方數的因子即可，比賽的時候忘記了因子也就是根号2加根号2等于根号8這種情況。

• 代碼

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
 
using namespace std;

int main(){
    int n;
    cin >> n;
    int res = 1;
    int cnt = 0;
    while(res * res <= n) {
    	for(int i = 1;i <= res;i++) {
    		if(res * res % i == 0) {
    			cnt += 2;
    		}
    	}
    	cnt--;
    	res++;
    }
    cout << cnt << endl;
    return 0;
}