UVALive 6179 Windmill Animation 规律题

规律题"/>

UVALive 6179 Windmill Animation 规律题

题目链接：点击打开链接

打表找规律

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const double Pi = acos(-1.0);
typedef long long ll;
const int N = 100;
int n, k, now, pre;
struct node{double x, y, ans;
}a[N];
double jiao;
double work(double x){while(x<0)x+=Pi;while(x>Pi)x-=Pi;return x;
}
double dis(node i, node j, node k){j.x -= i.x; j.y -= i.y;k.x -= i.x; k.y -= i.y;return acos((j.x*k.x+j.y*k.y)/(sqrt(j.x*j.x + j.y*j.y) * sqrt(k.x*k.x + k.y*k.y)));
}
bool xmul(node i, node j, node k){j.x -= i.x; j.y -= i.y;k.x -= i.x; k.y -= i.y;return (j.x*k.y - j.y*k.x) > 0;
}
void solve(){int ans = -1; double hehe;node X, Y;X.x = a[now].x + 1000.0*cos(jiao);Y.x = a[now].x + 1000.0*cos(jiao+Pi);X.y = a[now].y + 1000.0*sin(jiao);Y.y = a[now].y + 1000.0*sin(jiao+Pi);for(int i = 1; i <= n; i++) if(i!=now){if(i==pre) {a[i].ans = Pi;}else {//     double a1 = dis(a[now],  X, a[i]), a2 = dis(a[now], Y, a[i]);		printf("a[%d] : %.6f %.6f\n", i, a1, a2);if(xmul(a[now], X, a[i]))a[i].ans = work(dis(a[now],  X, a[i]));elsea[i].ans = work(dis(a[now],  Y, a[i]));}if(ans == -1 || hehe > a[i].ans){ans = i;hehe = a[i].ans;}}jiao += a[ans].ans;jiao = work(jiao);pre = now;now = ans;
}
int main(){int T, Cas;scanf("%d",&T);while(T--){scanf("%d %d %d %d %lf",&Cas,&n,&k,&now,&jiao);jiao = jiao/180.0*Pi;for(int i = 1; i <= n; i++){int num; double x,y;scanf("%d %lf %lf",&num,&x,&y);a[num].x = x;a[num].y = y;}pre = -1;printf("%d",Cas);while(k--){solve();printf(" %d", now);}puts("");}return 0;
}
/**/