Submission #448088

#	Time	Username	Problem	Language	Result	Execution time	Memory
448088		Antekb	Geometrija (COCI21_geometrija)	C++14	50 / 110	1084 ms	332 KiB

geometrija

#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
typedef long long ll;
typedef long double ld;

struct pii{
	int x, y;
	pii(int x, int y): x(x), y(y){}
	pii operator -(pii a){return pii(x-a.x, y-a.y);}
	bool operator <(pii a){return (x<a.x || (x==a.x && y<a.y));}
	ld dl(){return sqrt(x*1ll*x+y*1ll*y);}
};
ll cross(pii a, pii b){
	return a.x*1ll*b.y-a.y*1ll*b.x;
}
ll cross(pii a, pii b, pii c){
	return cross(b-a, c-a);
}
int sgn(ll a){
	if(a==0)return 0;
	return a/abs(a);
}
ll dot(pii a, pii b){
	return a.x*1ll*b.x+b.y*1ll*a.y;
}
ll dot(pii a, pii b, pii c){
	return dot(b-a, c-a);
}
typedef pair<pii, pii> odc;
vector<pii> V;
bool check(odc tt){
	vector<ld> A, B;
	for(int i=0; i<V.size(); i++){
		ll t=sgn(cross(tt.st, V[i], tt.nd));
		if(t>0){
			A.push_back(dot(tt.st, tt.nd, V[i])/(V[i]-tt.st).dl());
			B.push_back(dot(tt.nd, tt.st, V[i])/(V[i]-tt.nd).dl());
		}
	}
	sort(A.begin(), A.end());
	sort(B.begin(), B.end());
	//cout<<tt.st.x<<" "<<tt.st.y<<" "<<tt.nd.x<<" "<<tt.nd.y<<"\n";
	//cout<<A.size()<<"\n";
	for(int i=0; i<V.size(); i++){
		ll t=sgn(cross(tt.st, V[i], tt.nd));
		if(t<0){
			ld k=dot(tt.st, tt.nd, V[i])/(V[i]-tt.st).dl(), l=dot(tt.nd, tt.st, V[i])/(V[i]-tt.nd).dl();
			k=-k;
			l=-l;
			if(lower_bound(A.begin(), A.end(), k)-A.begin()+lower_bound(B.begin(), B.end(), l)-B.begin()!=A.size()){
				return 0;
			}
		}
	}
	return 1;
}
int main(){
	int n;
	cin>>n;
	V.resize(n, pii(0, 0));
	for(pii &i:V){
		cin>>i.x>>i.y;
	}
	int ans=0;
	for(int i=0; i<n; i++){
		for(int j=i+1; j<n; j++){
			ans+=check(odc(V[i], V[j]));
		}
	}
	cout<<ans;
}

Compilation message (stderr)

geometrija.cpp: In function 'bool check(odc)':
geometrija.cpp:35:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pii>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~
geometrija.cpp:46:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pii>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~
geometrija.cpp:52:96: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__normal_iterator<long double*, std::vector<long double> >::difference_type' {aka 'long int'} and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |    if(lower_bound(A.begin(), A.end(), k)-A.begin()+lower_bound(B.begin(), B.end(), l)-B.begin()!=A.size()){
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

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