Submission #776556

#	Time	Username	Problem	Language	Result	Execution time	Memory
776556		jamielim	Dragon 2 (JOI17_dragon2)	C++14	0 / 100	896 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;

double road(int x){
	double m=(double)(e2-e1)/(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){
		//printf("a\n");
		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{
		//printf("b\n");
		double m=(double)(p2.se-p1.se)/(double)(p2.fi-p1.fi);
		if(d1==d2){
			double y=m*(d1-p2.fi)+p2.se;
			if(e1<y-EPS&&y+EPS<e2)return 1;
		}else{
			if(p1.fi<p2.fi){
				double a=p1.se,b=m*(d2-p2.fi)+p2.se;
				if(p1.fi<d1){
					a=m*(d1-p2.fi)+p2.se;
					if(a+EPS<e1&&e2<b-EPS)return 1;
					if(a-EPS>e1&&e2>b+EPS)return 1;
				}else{
					double r=road(p1.fi);
					//printf("%lf %lf %d %lf\n",a,r,e2,b);
					if(a<r-EPS&&e2<b-EPS)return 1;
					if(a>r+EPS&&e2>b+EPS)return 1;
				}
			}else{
				double a=m*(d1-p2.fi)+p2.se,b=p1.se;
				if(p1.fi>d2){
					b=m*(d2-p2.fi)+p2.se;
					if(a+EPS<e1&&e2<b-EPS)return 1;
					if(a-EPS>e1&&e2>b+EPS)return 1;
				}else{
					double r=road(p1.fi);
					if(a+EPS<e1&&r<b-EPS)return 1;
					if(a-EPS>e1&&r>b+EPS)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:77:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
dragon2.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |   scanf("%d%d%d",&a,&b,&c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
dragon2.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |  scanf("%d%d%d%d",&d1,&e1,&d2,&e2);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:105:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
dragon2.cpp:107:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |   scanf("%d%d",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~

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