oj.uz

답안 #537597

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
537597 2022-03-15T09:29:18 Z jamezzz Planine (COCI21_planine) C++17
0 / 110
 4 ms 1072 KB 
#include <bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define INF 1023456789
typedef long long ll;
typedef long double ld;
typedef pair<ld,ld> ii;

int n,h,x[1000005],y[1000005];

struct line{
	ll x1,x2,y1,y2;
	int cross(line &o){//where does this line intersect
		ll x3=o.x1,x4=o.x2,y3=o.y1,y4=o.y2;
		if((x1-x2)*(y3-y4)==(x3-x4)*(y1-y2))return 2;//parallel
		ll num=(y3-y4)*(y1*(y1-y2)-x1*(x1-x2))-(y1-y2)*(y3*(y3-y4)-x3*(x3-x4));
		ll den=(y1-y2)*(x3-x4)-(y3-y4)*(x1-x2);
		if(num==h*den)return 0;//intersect exactly
		if((den>0&&num<h*den)||(den<0&&num>h*den))return 1;//intersect above
		if((den>0&&num>h*den)||(den<0&&num<h*den))return -1;//intersect below
	}
	bool cmp(line &o){
		if(x1<o.x1){
			if(cross(o)<=0)return false;
			else return true;
		}
		else{
			if(cross(o)==-1)return true;
			else return false;
		}
	}
	void print(){
		pf("{%lld %lld %lld %lld} ",x1,y1,x2,y2);
	}
};

struct valley{
	int i;
	line l1,l2;
	void print(){
		pf("%d: ",i);
		l1.print();
		l2.print();
		pf("\n");
	}
};

vector<valley> r;

int main(){
	sf("%d%d",&n,&h);
	for(int i=1;i<=n;++i)sf("%d%d",&x[i],&y[i]);
	for(int i=3;i<n;i+=2){
		line l1={x[i],x[i-1],y[i],y[i-1]};
		line l2={x[i],x[i+1],y[i],y[i+1]};
		r.pb({i,l1,l2});
	}
	sort(all(r),[](valley &a,valley &b){
		return a.l2.cmp(b.l2);
	});
	/*
	for(valley &i:r)i.print();
	for(int i=0;i<3;++i){
		for(int j=0;j<3;++j)pf("%d ",r[i].l2.cross(r[j].l2));
		pf("\n");
	}
	for(int i=0;i<3;++i){
		for(int j=0;j<3;++j)pf("%d ",r[i].l2.cmp(r[j].l2));
		pf("\n");
	}
	*/
	int ans=0;
	line pv=r[0].l1;
	pv.x1-=1;pv.x2-=1;
	for(int i=0;i<sz(r);++i){
		if(pv.cmp(r[i].l1)==1){
			++ans;pv=r[i].l2;
		}
	}
	pf("%d\n",ans);
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:58:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |  sf("%d%d",&n,&h);
      |    ^
Main.cpp:59:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |  for(int i=1;i<=n;++i)sf("%d%d",&x[i],&y[i]);
      |                         ^
Main.cpp: In member function 'int line::cross(line&)':
Main.cpp:28:2: warning: control reaches end of non-void function [-Wreturn-type]
   28 |  }
      |  ^

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 1072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 1072 KB Output isn't correct
2 Halted 0 ms 0 KB -