Submission #448089

#	Time	Username	Problem	Language	Result	Execution time	Memory
448089		Antekb	Geometrija (COCI21_geometrija)	C++14	110 / 110	396 ms	708 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));}
	bool operator ==(pii a){return 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;
}
pair<vector<pii>, vector<pii> > hull(){
	sort(V.begin(), V.end());
	vector<pii> ans, ans2;
	sort(V.begin()+1, V.end(), [](pii A, pii B){return cross(A-V[0], B-V[0])>0;});
	ans.push_back(V[0]);
	ans.push_back(V[1]);
	//for(int i=0; i<V.size(); i++)cout<<V[i].x<<" "<<V[i].y<<"\n";
	for(int i=2; i<V.size(); i++){
		while(ans.size()>=2 && cross(ans.back(), ans[ans.size()-2], V[i])>0){
			ans2.push_back(ans.back());
			ans.pop_back();
		}
		ans.push_back(V[i]);
	}
	return {ans, ans2};
}
typedef array<pii, 3> tri;
int main(){
	int n;
	cin>>n;
	V.resize(n, pii(0, 0));
	for(pii &i:V){
		cin>>i.x>>i.y;
	}
	auto h=hull();
	assert(h.st.size()>2);
	//cout<<h.st.size();
	vector<tri> tra;
	for(int i=2; i<h.st.size(); i++){
		tra.push_back({h.st[0], h.st[i-1], h.st[i]});
	}
	//cout<<tra.size();
	for(pii i:h.nd){
		bool b=0;
		for(int j=0; j<tra.size(); j++){
			int a1=sgn(cross(i, tra[j][0], tra[j][1])),a2=sgn(cross(i, tra[j][1], tra[j][2])),a3=sgn(cross(i, tra[j][2], tra[j][0]));
			if(a1==a2 && a2==a3){
				b=1;
				tra.push_back({i, tra[j][0], tra[j][1]});
				tra.push_back({i, tra[j][1], tra[j][2]});
				tra.push_back({i, tra[j][2], tra[j][0]});
				swap(tra[j], tra.back());
				tra.pop_back();
				break;
			}
		}
		assert(b==1);
	}
	//cout<<tra.size();
	vector<odc> todo;
	for(auto i:tra){
		todo.push_back({i[0], i[1]});
		todo.push_back({i[1], i[2]});
		todo.push_back({i[2], i[0]});
	}
	for(auto &i:todo){
		if(i.st<i.nd)swap(i.st, i.nd);
	}
	sort(todo.begin(), todo.end(), [](odc a, odc b){return a.st<b.st || (a.st==b.st && a.nd<b.nd);});
	int ans=0;
	for(int i=0; i<todo.size(); i++){
		if(i==0 || !(todo[i].st==todo[i-1].st) || !(todo[i].nd==todo[i-1].nd)){
			//cout<<"a";
			ans+=check(todo[i]);
		}
	}
	cout<<ans;
}

Compilation message (stderr)

geometrija.cpp: In function 'bool check(odc)':
geometrija.cpp:36:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pii>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~
geometrija.cpp:47:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pii>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~
geometrija.cpp:53: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]
   53 |    if(lower_bound(A.begin(), A.end(), k)-A.begin()+lower_bound(B.begin(), B.end(), l)-B.begin()!=A.size()){
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
geometrija.cpp: In function 'std::pair<std::vector<pii>, std::vector<pii> > hull()':
geometrija.cpp:67:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pii>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for(int i=2; i<V.size(); i++){
      |               ~^~~~~~~~~
geometrija.cpp: In function 'int main()':
geometrija.cpp:88:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pii>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |  for(int i=2; i<h.st.size(); i++){
      |               ~^~~~~~~~~~~~
geometrija.cpp:94:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<pii, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |   for(int j=0; j<tra.size(); j++){
      |                ~^~~~~~~~~~~
geometrija.cpp:120:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<pii, pii> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |  for(int i=0; i<todo.size(); i++){
      |               ~^~~~~~~~~~~~

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