Submission #392124

#	Time	Username	Problem	Language	Result	Execution time	Memory
392124		soroush	Geometrija (COCI21_geometrija)	C++17	20 / 110	38 ms	820 KiB

geometrija

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 2100;
const ll mod = 1e9+7;
const ld PI = acos((ld)-1);

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

int n;

struct point{ 
	ll x , y;
}p[maxn]; 

bool bad[maxn][maxn];

bool ccw(point A,point B,point C){
    return (C.y-A.y)*(B.x-A.x) > (B.y-A.y)*(C.x-A.x);
}

bool boom (point A,point B,point C,point D){
    return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D);
}

time_t start , now;

int32_t main(){
	migmig;
	cin >> n;
	for(int i = 1 ; i <= n ; i ++){
		cin >> p[i].x >> p[i].y;
	}
	time(&start); 
	int ans = 0;
	for(int i = 1 ; i <= n ; i ++){
		for(int j = i + 1 ; j <= n ; j ++){
			time(&now);
			if(now - start > 0.98)break;
			for(int k = 1 ; k <= n ; k ++){
				for(int l = k+1 ; l <= n ; l ++){
					if(i^k and i^l and j^k and j^l and boom(p[i] , p[j] , p[k] , p[l])){
						bad[k][l] = bad[i][j] = 1;
					}
					if(bad[i][j])break;
				}
				if(bad[i][j])break;
			}
		}
	}
	for(int i = 1 ; i <= n ; i ++){
		for(int j = i + 1 ; j <= n ; j ++){
			ans += !bad[i][j];
		}
	}
	cout << ans;
	return(0);
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60