Submission #71655

#	Time	Username	Problem	Language	Result	Execution time	Memory
71655		yogahmad	Relay (COI16_relay)	C++14	0 / 100	2068 ms	3160 KiB

relay

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fbo find_by_order
#define ook order_of_key
#define f first
#define s second
#define pb push_back
#define reset(a,b) memset(a,b,sizeof a);
#define MOD 1000000007
#define MID (l+r)/2
#define ALL(x) x.begin(),x.end()
#define debug(x) cout<<#x<<" = "<<(x)<<endl
#define mx 100003
#define pc(x) putchar_unlocked(x);
typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> pbds;

struct point{
	long long x, y;
	point() { }
	point(long long _x, long long _y): x(_x), y(_y) { }
	friend point operator+(const point &x, const point &y) { return point(x.x + y.x, x.y + y.y); }
	friend point &operator+=(point &x, const point &y) { x.x += y.x, x.y += y.y; return x; }
	friend point operator-(const point &x, const point &y) { return point(x.x - y.x, x.y - y.y); }
	friend point &operator-=(point &x, const point &y) { x.x -= y.x, x.y -= y.y; return x; }
	friend bool operator<(const point &x, const point &y) { if (x.x == y.x) return x.y < y.y; return x.x < y.x; }
	friend long long operator^(const point &x, const point &y) { return x.x * y.x + x.y * y.y; }//Dot Product
	friend long long operator*(const point &x, const point &y) { return x.x * y.y - x.y * y.x; }//Cross Product
	friend bool operator==(const point &x,point &y){return x.x==y.x && x.y==y.y;}
}titik[mx],kapal[mx],o;

long long arah(point a,point b,point c){
	return (b-a)*(c-a);
}

bool cmp(point a,point b){
	return arah(o,a,b)<0;
}

bool yo(vector<point>ve,point aa,point bb){
	sort(ALL(ve));
	o=ve[0];
	sort(ve.begin()+1,ve.end(),cmp);
	vector<point>ret;
	ret.pb(ve[0]);
	ret.pb(ve[1]);
	ret.pb(ve[2]);
	int cnt=3;
//	debug(ret.size());
	for(int i=3;i<ve.size();i++){
		assert(ret.size()==cnt);
		while(cnt>=2 && arah(ret[cnt-2],ret[cnt-1],ve[i])>=0)ret.pop_back(),cnt--;
		cnt++;
		ret.pb(ve[i]);
	}
	int hit=0,di=-1;
//	debug(ret.size());
	for(auto i:ret){
		if(i==aa || i==bb){
			if(di==-1)di=hit;
			else{
				if(abs(hit-di)==1){
					return true;
				}
				if(di==0 && hit==ret.size()-1)return true;
				return false;
			}
		}
		hit++;
	}
	return true;
}

int n,m;
vector<int>g[mx];

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%lld%lld",&kapal[i].x,&kapal[i].y);
	scanf("%d",&m);
	assert(n<=300 && m<=300);
	for(int i=1;i<=m;i++)scanf("%lld%lld",&titik[i].x,&titik[i].y);
	vector<point>ve;
	for(int k=1;k<=m;k++){
		ve.pb(titik[k]);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j)continue;
			ve.pb(kapal[i]);
			ve.pb(kapal[j]);
		//	debug(i);
		//	debug(j);
			if(yo(ve,kapal[i],kapal[j])){
				g[i].pb(j);
			//	if(i==1)debug(j);
			}
			ve.pop_back();
			ve.pop_back();
		}
	}
	set<int>jaw,aa;
	jaw.insert(1);
	for(int i:g[1])jaw.insert(i);
	for(int i:jaw){
		aa.insert(i);
		for(int j:g[i])aa.insert(j);
	}
	cout<<aa.size()-1<<endl;
}

Compilation message (stderr)

relay.cpp: In function 'bool yo(std::vector<point>, point, point)':
relay.cpp:52:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=3;i<ve.size();i++){
              ~^~~~~~~~~~
In file included from /usr/include/c++/7/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp:45:0,
                 from /usr/include/c++/7/ext/pb_ds/detail/container_base_dispatch.hpp:90,
                 from /usr/include/c++/7/ext/pb_ds/assoc_container.hpp:48,
                 from relay.cpp:2:
relay.cpp:53:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   assert(ret.size()==cnt);
          ~~~~~~~~~~^~~
relay.cpp:67:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(di==0 && hit==ret.size()-1)return true;
                 ~~~^~~~~~~~~~~~~~
relay.cpp: In function 'int main()':
relay.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
relay.cpp:81:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++)scanf("%lld%lld",&kapal[i].x,&kapal[i].y);
                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
relay.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&m);
  ~~~~~^~~~~~~~~
relay.cpp:84:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=m;i++)scanf("%lld%lld",&titik[i].x,&titik[i].y);
                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 18
• Subtask 2: 0 / 19
• Subtask 3: 0 / 20
• Subtask 4: 0 / 43