Submission #776570

#	Time	Username	Problem	Language	Result	Execution time	Memory
776570		jamielim	Dragon 2 (JOI17_dragon2)	C++14	0 / 100	1254 ms	262144 KiB

dragon2

#include <bits/stdc++.h>
using namespace std;

#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
typedef pair<int,int> ii;
typedef long long ll;
typedef unsigned long long ull;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const ll MOD=1000000007;
const double EPS=1E-10;

int n,m;
vector<ii> tribe[30005];
vector<int> adj[30005];
int d1,e1,d2,e2;
int q;

inline double road(int x){
	double m=(double)(e2-e1)/(double)(d2-d1);
	return m*(x-d1)+e1;
}

inline bool ixn(ii p1,ii p2){
	//printf("try %d %d %d %d\n",p1.fi,p1.se,p2.fi,p2.se);
	if(p1.fi==p2.fi){
		if(d1>p1.fi||d2<p1.fi)return 0;
		// x coordinate is correct
		if(p1.se<p2.se){
			if(p2.se<road(p1.fi)-EPS)return 1;
		}else{
			if(p2.se>road(p1.fi)-EPS)return 1;
		}
	}else{
		if(d1==d2){
			if(p1.fi<p2.fi&&p2.fi>d1)return 0;
			if(p1.fi>p2.fi&&p2.fi<d1)return 0;
			double m=(double)(p2.se-p1.se)/(double)(p2.fi-p1.fi);
			double y=m*(d1-p2.fi)+p2.se;
			if(e1<y-EPS&&y+EPS<e2)return 1;
		}else{
			double m1=(double)(e2-e1)/(double)(d2-d1);
			double m2=(double)(p2.se-p1.se)/(double)(p2.fi-p1.fi);
			double c1=e1-m1*d1,c2=p1.se-m2*p1.fi;
			if(m1==m2){
				return 0;
			}
			double x=(c1-c2)/(m2-m1);
			if(p1.fi<p2.fi&&p1.fi<x-EPS){
				if(d1<x-EPS&&x+EPS<d2)return 1;
			}else if(p1.fi>p2.fi&&p1.fi>x+EPS){
				if(d1<x-EPS&&x+EPS<d2)return 1;
			}
		}
	}
	return 0;
}

int main(){
	scanf("%d%d",&n,&m);
	int a,b,c;
	for(int i=0;i<n;i++){
		scanf("%d%d%d",&a,&b,&c);
		tribe[c].pb(a,b);
	}
	scanf("%d%d%d%d",&d1,&e1,&d2,&e2);
	if(d1>d2){
		swap(d1,d2);
		swap(e1,e2);
	}else if(d1==d2){
		if(e1>e2)swap(e1,e2);
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++){
			if(i==j)continue;
			for(ii k:tribe[i]){
				for(ii l:tribe[j]){
					if(ixn(k,l)){
					//	printf("1\n");
						adj[i].pb(j);
					}else{
					//	printf("0\n");
					}
				}
			}
		}
	}
	scanf("%d",&q);
	while(q--){
		scanf("%d%d",&a,&b);
		int ans=0;
		for(int i:adj[a]){
			if(i==b)ans++;
		}
		printf("%d\n",ans);
	}
}

Compilation message (stderr)

dragon2.cpp: In function 'int main()':
dragon2.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
dragon2.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |   scanf("%d%d%d",&a,&b,&c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
dragon2.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |  scanf("%d%d%d%d",&d1,&e1,&d2,&e2);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
dragon2.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |   scanf("%d%d",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40