列表

详情

NC207613. windmill

描述

SDZ is very bored at home recently. He always watches videos of animals such as violent elephants at station B. Just last week, SDZ found a game called "Windmill".The following describes what a "windmill" is.
There are some point (at least two) in the plane. Assume that no three points are collinear. A windmill is a process that starts with a line l going through a single point P in the plane. The line rotated clockwise about the point P until the first time that the line meets some other point in the plane.This point, Q, takes over as the new pivot, and the line now rotates clockwise about Q, until it next meets point.
SDZ found that sometimes the windmill can hit all the points, but sometimes it can't. For example, the windmill has been rotating outside the point, so you can't touch the point inside. SDZ thinks it's amazing, so let it be.
He wants to know which point on the line is when the line L rotates α. We guarantee that there is only one point on the line at the beginning and end.

输入描述

The first line contains one integer n that there are n points in total.
The first line contains three integers x, y and β to indicate the point P and the angle formed by the anticlockwise direction of line L and X-axis (angle representation) ( 1 < = n < = 1000, -1000 < = x, y < = 1000; 0 < = β < 360)
The next n-1 lines, each line contains two integers x, y, representing the coordinates of the point
The last line contains α to indicate the rotation angle of the line L. (0<=α<=360000)

输出描述

Print the only line containing two integers x and y to indicate the point .

示例1

输入: 

3
1 0 30
0 0
1 1
45

输出: 

0 0

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 813ms, 内存消耗: 628K, 提交时间: 2020-06-07 17:53:37 

#include<bits/stdc++.h>
using namespace std;
struct point{
	double x,y;
	void sc(){
		scanf("%lf%lf",&x,&y);
	}
	double len(){
		return sqrt(x*x+y*y);
	}
	double cross(point b){
		return x*b.y-y*b.x;
	}
	double dot(point b){
		return x*b.x+y*b.y;
	}
	point operator-(point b){
		return {x-b.x,y-b.y};
	}
}p[2000];
double angle(point a,point b){
	const double pi=acos(-1);
	double t=atan2(a.y,a.x)-atan2(b.y,b.x);
	t=fmod(t,2*pi);
	if(t<0)t+=2*pi;
	return t;
}
int main(){
	int n;
	scanf("%d",&n);
	point o;
	o.sc();
	double a;
	scanf("%lf",&a);
	const double pi=acos(-1);
	a=a*pi/180;
	p[0]=o;
	for(int i=1;i<n;i++){
		p[i].sc();
	}
	point v={cos(a),sin(a)};
	int pos=0;
	scanf("%lf",&a);
	a=fmod(a,360);
	a=a*pi/180;
	int op=0,opp=0;
	while(a>0){
		double cur=1e9;
		for(int i=0;i<n;i++){
			if(i==op||i==opp)continue;
			double d=min(angle(v,o-p[i]),angle(v,p[i]-o));
			if(d<cur){
				pos=i;
				cur=d;
			}
		}
		if(a<cur){
			cout<<o.x<<' '<<o.y<<endl;
			return 0;
		}
		a-=cur;
		opp=op;
		v=p[pos]-o;
		o=p[pos];
		op=pos;
	}
	cout<<o.x<<' '<<o.y;
}

上一题

© 2025 nowcoder.com