首页 > ACM题库 > HDU-杭电 > HDU 3961-Crisis[解题报告]HOJ
2015
04-14

HDU 3961-Crisis[解题报告]HOJ

Crisis

问题描述 :

Warning! Warning! The new round of sunspot radiation is now coming and that put the life of all creatures on the earth in great danger. In order to protect our mother earth, the Association of Cosmos Monitoring(ACM) has decided to build a huge barrier floating in the sky to block the radiation. Since the earth is extremely large and the barrier may not be able to cover the whole planet, the ACM wants to know how many areas will still be under the radiation so that they could evacuate the people in those areas.
Board Game Dice

To simplify the problem, you may assume the earth, the barrier and the sun are in the same 2D plane. The sun is considered as a point radiation source. The barrier is a simple polygon which has N endpoints and the earth is a circle. As we all know, to keep a huge barrier on the sky against the gravity, the barrier has to do uniform circular motion surround the earth. Also the barrier itself rotates surround its gravity center at a certain speed.
Board Game Dice

You need pay attention to the next points:

The revolution and rotation are both anticlockwise.

There is always a line dividing the plane into two half-plane, making the barrier in one, and the earth in the other.

The sun is exactly out of the barrier and the earth at any time.

The revolution is translational motion.

To calculate the movement of the huge barrier is very difficult, so the ACM needs you to write a program to calculate this problem and heal the world. Given the current location of the sun, the earth and the barrier, the periods of the barrier traveling around the earth and its rotation, and the time when the radiation outbreak from now, the ACM wants you to tell them the arc length of the areas which are under radiation.

输入:

Input contains several test cases (≤1000). The first line of each case contains 5 integer numbers Xs, Ys, Xe, Ye, Re. (Xs, Ys) is the coordinate of the sun (-10000 ≤ x, y, r ≤ 10000, similarly hereinafter), (Xe, Ye) is the coordinate of the earth’s core, Re indicate the radius of the earth.

The second line of the input contains 4 integer numbers N (≤100), T1, T2, T. N indicate the number of the barrier’s endpoints, T1 is the barrier’s period of revolution, T2 is the barrier’s rotation period, T is the time when the radiation outbreak from now. The next N lines, each line consists of two integers xi and yi indicate the coordinate of the i-th endpoint of the barrier, and the endpoints will be given by the clockwise or anticlockwise order.

输出:

Input contains several test cases (≤1000). The first line of each case contains 5 integer numbers Xs, Ys, Xe, Ye, Re. (Xs, Ys) is the coordinate of the sun (-10000 ≤ x, y, r ≤ 10000, similarly hereinafter), (Xe, Ye) is the coordinate of the earth’s core, Re indicate the radius of the earth.

The second line of the input contains 4 integer numbers N (≤100), T1, T2, T. N indicate the number of the barrier’s endpoints, T1 is the barrier’s period of revolution, T2 is the barrier’s rotation period, T is the time when the radiation outbreak from now. The next N lines, each line consists of two integers xi and yi indicate the coordinate of the i-th endpoint of the barrier, and the endpoints will be given by the clockwise or anticlockwise order.

样例输入:

-11 -6 9 7 9
7 100 120 0
-5 -3
-3 -4
-1 -3
-1 -2
-2 -1
-3 0
-4 -1
-11 -6 9 7 9
7 100 120 95
-5 -3
-3 -4
-1 -3
-1 -2
-2 -1
-3 0
-4 -1

样例输出:

13.93
13.45

/** Micro Mezzo Macro Flation -- Overheated Economy ., Last Update: Dec. 20th 2012 **/ //{

/** Header .. **/ //{
#define LOCAL

#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>

using namespace std;

#define REP(i, n) for (int i=0;i<int(n);++i)
#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)
#define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)
#define REP_1(i, n) for (int i=1;i<=int(n);++i)
#define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i)
#define DWN_1(i, b, a) for (int i=int(b);i>=int(a);--i)
#define REP_C(i, n) for (int n____=int(n),i=0;i<n____;++i)
#define FOR_C(i, a, b) for (int b____=int(b),i=a;i<b____;++i)
#define DWN_C(i, b, a) for (int a____=int(a),i=b-1;i>=a____;--i)
#define REP_N(i, n) for (i=0;i<int(n);++i)
#define FOR_N(i, a, b) for (i=int(a);i<int(b);++i)
#define DWN_N(i, b, a) for (i=int(b-1);i>=int(a);--i)
#define REP_1_C(i, n) for (int n____=int(n),i=1;i<=n____;++i)
#define FOR_1_C(i, a, b) for (int b____=int(b),i=a;i<=b____;++i)
#define DWN_1_C(i, b, a) for (int a____=int(a),i=b;i>=a____;--i)
#define REP_1_N(i, n) for (i=1;i<=int(n);++i)
#define FOR_1_N(i, a, b) for (i=int(a);i<=int(b);++i)
#define DWN_1_N(i, b, a) for (i=int(b);i>=int(a);--i)
#define REP_C_N(i, n) for (int n____=(i=0,int(n));i<n____;++i)
#define FOR_C_N(i, a, b) for (int b____=(i=0,int(b);i<b____;++i)
#define DWN_C_N(i, b, a) for (int a____=(i=b-1,int(a));i>=a____;--i)
#define REP_1_C_N(i, n) for (int n____=(i=1,int(n));i<=n____;++i)
#define FOR_1_C_N(i, a, b) for (int b____=(i=1,int(b);i<=b____;++i)
#define DWN_1_C_N(i, b, a) for (int a____=(i=b,int(a));i>=a____;--i)

#define ECH(it, A) for (__typeof(A.begin()) it=A.begin(); it != A.end(); ++it)
#define REP_S(i, str) for (char*i=str;*i;++i)
#define REP_L(i, hd, nxt) for (int i=hd;i;i=nxt[i])
#define REP_G(i, u) REP_L(i,hd[u],suc)
#define DO(n) for ( int ____n ## __line__ = n; ____n ## __line__ -- ; )
#define REP_2(i, j, n, m) REP(i, n) REP(j, m)
#define REP_2_1(i, j, n, m) REP_1(i, n) REP_1(j, m)
#define REP_3(i, j, k, n, m, l) REP(i, n) REP(j, m) REP(k, l)
#define REP_3_1(i, j, k, n, m, l) REP_1(i, n) REP_1(j, m) REP_1(k, l)

#define ALL(A) A.begin(), A.end()
#define LLA(A) A.rbegin(), A.rend()
#define CPY(A, B) memcpy(A, B, sizeof(A))
#define INS(A, P, B) A.insert(A.begin() + P, B)
#define ERS(A, P) A.erase(A.begin() + P)
#define BSC(A, x) (lower_bound(ALL(A), x) - A.begin())
#define CTN(T, x) (T.find(x) != T.end())
#define SZ(A) int(A.size())
#define PB push_back
#define MP(A, B) make_pair(A, B)
#define PTT pair<T, T>
#define fi first
#define se second

#define Rush for(int ____T=RD(); ____T--;)

#define Display(A, n, m) { \
	REP(i, n){		 \
 REP(j, m) cout << A[i][j] << " "; \
 cout << endl;				 \
	}						 \
}

#define Display_1(A, n, m) {				 \
	REP_1(i, n){		 \
 REP_1(j, m) cout << A[i][j] << " "; \
		cout << endl;		 		\
	}						 \
}

#pragma comment(linker, "/STACK:36777216")
//#pragma GCC optimize ("O2")
#define Ruby system("ruby main.rb")
#define Haskell system("runghc main.hs")
#define Python system("python main.py")
#define Pascal system("fpc main.pas")

typedef long long LL;
//typedef long double DB;
typedef double DB;
typedef unsigned UINT;
typedef unsigned long long ULL;

typedef vector<int> VI;
typedef vector<char> VC;
typedef vector<string> VS;
typedef vector<LL> VL;
typedef vector<DB> VF;
typedef set<int> SI;
typedef set<string> SS;
typedef map<int, int> MII;
typedef map<string, int> MSI;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

template<class T> inline T& RD(T &);
template<class T> inline void OT(const T &);
inline LL RD(){LL x; return RD(x);}
inline DB& RF(DB &x){scanf("%lf", &x); return x;}
inline DB RF(){DB x; return RF(x);}
inline char* RS(char *s);
inline char& RC(char &c);
inline char RC();
inline char& RC(char &c){scanf(" %c", &c); return c;}
inline char RC(){char c; return RC(c);}
//inline char& RC(char &c){c = getchar(); return c;}
//inline char RC(){return getchar();}

template<class T0, class T1> inline T0& RD(T0 &x0, T1 &x1){RD(x0), RD(x1); return x0;}
template<class T0, class T1, class T2> inline T0& RD(T0 &x0, T1 &x1, T2 &x2){RD(x0), RD(x1), RD(x2); return x0;}
template<class T0, class T1, class T2, class T3> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3){RD(x0), RD(x1), RD(x2), RD(x3); return x0;}
template<class T0, class T1, class T2, class T3, class T4> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4); return x0;}
template<class T0, class T1, class T2, class T3, class T4, class T5> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5); return x0;}
template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5), RD(x6); return x0;}
template<class T0, class T1> inline void OT(const T0 &x0, const T1 &x1){OT(x0), OT(x1);}
template<class T0, class T1, class T2> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2){OT(x0), OT(x1), OT(x2);}
template<class T0, class T1, class T2, class T3> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3){OT(x0), OT(x1), OT(x2), OT(x3);}
template<class T0, class T1, class T2, class T3, class T4> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3, const T4 &x4){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4);}
template<class T0, class T1, class T2, class T3, class T4, class T5> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3, const T4 &x4, const T5 &x5){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5);}
template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3, const T4 &x4, const T5 &x5, const T6 &x6){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5), OT(x6);}
inline char& RC(char &a, char &b){RC(a), RC(b); return a;}
inline char& RC(char &a, char &b, char &c){RC(a), RC(b), RC(c); return a;}
inline char& RC(char &a, char &b, char &c, char &d){RC(a), RC(b), RC(c), RC(d); return a;}
inline char& RC(char &a, char &b, char &c, char &d, char &e){RC(a), RC(b), RC(c), RC(d), RC(e); return a;}
inline char& RC(char &a, char &b, char &c, char &d, char &e, char &f){RC(a), RC(b), RC(c), RC(d), RC(e), RC(f); return a;}
inline char& RC(char &a, char &b, char &c, char &d, char &e, char &f, char &g){RC(a), RC(b), RC(c), RC(d), RC(e), RC(f), RC(g); return a;}
inline DB& RF(DB &a, DB &b){RF(a), RF(b); return a;}
inline DB& RF(DB &a, DB &b, DB &c){RF(a), RF(b), RF(c); return a;}
inline DB& RF(DB &a, DB &b, DB &c, DB &d){RF(a), RF(b), RF(c), RF(d); return a;}
inline DB& RF(DB &a, DB &b, DB &c, DB &d, DB &e){RF(a), RF(b), RF(c), RF(d), RF(e); return a;}
inline DB& RF(DB &a, DB &b, DB &c, DB &d, DB &e, DB &f){RF(a), RF(b), RF(c), RF(d), RF(e), RF(f); return a;}
inline DB& RF(DB &a, DB &b, DB &c, DB &d, DB &e, DB &f, DB &g){RF(a), RF(b), RF(c), RF(d), RF(e), RF(f), RF(g); return a;}
inline void RS(char *s1, char *s2){RS(s1), RS(s2);}
inline void RS(char *s1, char *s2, char *s3){RS(s1), RS(s2), RS(s3);}

template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}
template<class T0, class T1> inline void RST(T0 &A0, T1 &A1){RST(A0), RST(A1);}
template<class T0, class T1, class T2> inline void RST(T0 &A0, T1 &A1, T2 &A2){RST(A0), RST(A1), RST(A2);}
template<class T0, class T1, class T2, class T3> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3){RST(A0), RST(A1), RST(A2), RST(A3);}
template<class T0, class T1, class T2, class T3, class T4> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4);}
template<class T0, class T1, class T2, class T3, class T4, class T5> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5);}
template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5), RST(A6);}
template<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));}
template<class T0, class T1> inline void FLC(T0 &A0, T1 &A1, int x){FLC(A0, x), FLC(A1, x);}
template<class T0, class T1, class T2> inline void FLC(T0 &A0, T1 &A1, T2 &A2, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x);}
template<class T0, class T1, class T2, class T3> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x);}
template<class T0, class T1, class T2, class T3, class T4> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x);}
template<class T0, class T1, class T2, class T3, class T4, class T5> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x);}
template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x), FLC(A6, x);}
template<class T> inline void CLR(priority_queue<T, vector<T>, less<T> > &Q){while (!Q.empty()) Q.pop();}
template<class T> inline void CLR(priority_queue<T, vector<T>, greater<T> > &Q){while (!Q.empty()) Q.pop();}
template<class T> inline void CLR(T &A){A.clear();}
template<class T0, class T1> inline void CLR(T0 &A0, T1 &A1){CLR(A0), CLR(A1);}
template<class T0, class T1, class T2> inline void CLR(T0 &A0, T1 &A1, T2 &A2){CLR(A0), CLR(A1), CLR(A2);}
template<class T0, class T1, class T2, class T3> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3){CLR(A0), CLR(A1), CLR(A2), CLR(A3);}
template<class T0, class T1, class T2, class T3, class T4> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4);}
template<class T0, class T1, class T2, class T3, class T4, class T5> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5);}
template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5), CLR(A6);}
template<class T> inline void CLR(T &A, int n){REP(i, n) CLR(A[i]);}

template<class T> inline T& SRT(T &A){sort(ALL(A)); return A;}
template<class T, class C> inline T& SRT(T &A, C B){sort(ALL(A), B); return A;}
template<class T> inline T& UNQ(T &A){A.resize(unique(ALL(SRT(A))) - A.begin());return A;}

//}

/** Constant List .. **/ //{

const int MOD = 1000000007;
//int MOD = 99990001;
const int INF = 0x3f3f3f3f;
const LL INFF = 1LL << 60;
const DB EPS = 1e-9;
const DB OO = 1e15;
const DB PI = acos(-1.0); //M_PI;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

//}

/** Add On .. **/ //{
// <<= '0. Nichi Joo ., //{
template<class T> inline void checkMin(T &a,const T b){if (b<a) a=b;}
template<class T> inline void checkMax(T &a,const T b){if (a<b) a=b;}
template<class T> inline void checkMin(T &a, T &b, const T x){checkMin(a, x), checkMin(b, x);}
template<class T> inline void checkMax(T &a, T &b, const T x){checkMax(a, x), checkMax(b, x);}
template <class T, class C> inline void checkMin(T& a, const T b, C c){if (c(b,a)) a = b;}
template <class T, class C> inline void checkMax(T& a, const T b, C c){if (c(a,b)) a = b;}
template<class T> inline T min(T a, T b, T c){return min(min(a, b), c);}
template<class T> inline T max(T a, T b, T c){return max(max(a, b), c);}
template<class T> inline T min(T a, T b, T c, T d){return min(min(a, b), min(c, d));}
template<class T> inline T max(T a, T b, T c, T d){return max(max(a, b), max(c, d));}
template<class T> inline T sqr(T a){return a*a;}
template<class T> inline T cub(T a){return a*a*a;}
inline int Ceil(int x, int y){return (x - 1) / y + 1;}
//}
// <<= '1. Bitwise Operation ., //{
namespace BO{

inline bool _1(int x, int i){return bool(x&1<<i);}
inline bool _1(LL x, int i){return bool(x&1LL<<i);}
inline LL _1(int i){return 1LL<<i;}
inline LL _U(int i){return _1(i) - 1;};

inline int reverse_bits(int x){
 x = ((x >> 1) & 0x55555555) | ((x << 1) & 0xaaaaaaaa);
 x = ((x >> 2) & 0x33333333) | ((x << 2) & 0xcccccccc);
 x = ((x >> 4) & 0x0f0f0f0f) | ((x << 4) & 0xf0f0f0f0);
 x = ((x >> 8) & 0x00ff00ff) | ((x << 8) & 0xff00ff00);
 x = ((x >>16) & 0x0000ffff) | ((x <<16) & 0xffff0000);
 return x;
}

inline LL reverse_bits(LL x){
 x = ((x >> 1) & 0x5555555555555555LL) | ((x << 1) & 0xaaaaaaaaaaaaaaaaLL);
 x = ((x >> 2) & 0x3333333333333333LL) | ((x << 2) & 0xccccccccccccccccLL);
 x = ((x >> 4) & 0x0f0f0f0f0f0f0f0fLL) | ((x << 4) & 0xf0f0f0f0f0f0f0f0LL);
 x = ((x >> 8) & 0x00ff00ff00ff00ffLL) | ((x << 8) & 0xff00ff00ff00ff00LL);
 x = ((x >>16) & 0x0000ffff0000ffffLL) | ((x <<16) & 0xffff0000ffff0000LL);
 x = ((x >>32) & 0x00000000ffffffffLL) | ((x <<32) & 0xffffffff00000000LL);
 return x;
}

template<class T> inline bool odd(T x){return x&1;}
template<class T> inline bool even(T x){return !odd(x);}
template<class T> inline T low_bit(T x) {return x & -x;}
template<class T> inline T high_bit(T x) {T p = low_bit(x);while (p != x) x -= p, p = low_bit(x);return p;}
template<class T> inline T cover_bit(T x){T p = 1; while (p < x) p <<= 1;return p;}

inline int low_idx(int x){return __builtin_ffs(x);}
inline int low_idx(LL x){return __builtin_ffsll(x);}
inline int high_idx(int x){return low_idx(reverse_bits(x));}
inline int high_idx(LL x){return low_idx(reverse_bits(x));}
inline int clz(int x){return __builtin_clz(x);}
inline int clz(LL x){return __builtin_clzll(x);}
inline int ctz(int x){return __builtin_ctz(x);}
inline int ctz(LL x){return __builtin_ctzll(x);}
inline int parity(int x){return __builtin_parity(x);}
inline int parity(LL x){return __builtin_parityll(x);}
inline int lg2(int a){return 31 - clz(a);}
inline int lg2(LL a){return 63 - clz(a);}
inline int count_bits(int x){return __builtin_popcount(x);}
inline int count_bits(LL x){return __builtin_popcountll(x);}

} using namespace BO;//}
namespace SL{
 namespace KMP{

 void calc_pi(const char *P, int n, int *pi){
 for (int i = 1, j = pi[0] = -1; i < n; ++i){
 while (j >= 0 && P[i] != P[j+1]) j = pi[j];
 if (P[i] == P[j+1]) ++j;
 pi[i] = j;
 }
 //REP(i, n) cout << pi[i] << " "; cout << endl;
 }

 bool run(const char *T, int n, const char *P, int m, const int *pi){
 for (int i = 0, j = -1; i < n; ++i){
 while (j >= 0 && T[i] != P[j+1]) j = pi[j];
 if (T[i] == P[j+1]) ++j;
 if (j == m - 1) return true;
 }
 return false;
 }

 } //using namespace KMP;

 namespace Z{
 void calc_z(const char *P, int n, int *z){

 z[0] = n;

 for (int i = 1, l = 0, r = 0; i < n; ++i){
 if (i > r){
 for(l = r = i; r < n && P[r] == P[r - l];) ++r;
 z[i] = r - l, --r;
 }
 else {
 if (z[i - l] < r - i + 1) z[i] = z[i - l];
 else {
 for (l = i;r < n && P[r] == P[r - l];) ++r;
 z[i] = r - l, --r;
 }
 }
 }

 //REP(i, n) cout << z[i] << " "; cout << endl;
 }

 int run(const char *T, int n, const char *P, int m, const int *z){

 int ex; REP_C_N(ex, min(n, m)) if (T[ex] != P[ex]) break;

 int res = ex == m;

 for (int i = 1, l = 0, r = 0; i < n; ++i){
 if (i > r){
 for (l = r = i; r < n && T[r] == P[r - l];) ++r;
 ex = r - l, --r;
 }
 else {
 if (z[i - l] < r - i + 1) ex = z[i - l];
 else {
 for (l = i; r < n && T[r] == P[r - l];) ++r;
 ex = r - l, --r;
 }
 }
 if (ex == m) ++res;
 }

 return res;
 }
 } //using namespace Z;

 void Manacher(char s[], int n, int p[]){
 const int NN = 0;
 static char ss[NN*2+2]; int nn = 2*n+2;
 ss[0] = '$', ss[nn-1] = '#', ss[nn] = 0;
 REP(i, n) ss[i*2+1] ='#', ss[i*2+2] = s[i];
 int mx = 0, id = 0; FOR(i, 1, nn){
 p[i] = mx > i ? min(p[2*id-i], mx - i) : 1;
 while (ss[i+p[i]] == ss[i-p[i]]) ++p[i];
 if (i + p[i] > mx) mx = i + p[i], id = i;
 }
 }

} //using namespace SL;//}
// <<= '9. Comutational Geometry .,//{
namespace CG{

struct Po; struct Line; struct Seg;

inline int sgn(DB x){return x < -EPS ? -1 : x > EPS;}
inline int sgn(DB x, DB y){return sgn(x - y);}

struct Po{
 DB x, y; Po(DB _x=0, DB _y=0):x(_x), y(_y){}
 friend istream& operator >>(istream& in, Po &p){return in >> p.x >> p.y;}
 friend ostream& operator <<(ostream& out, Po p){return out << "(" << p.x << ", " << p.y << ")";}
 bool operator ==(const Po& r)const{return !sgn(x-r.x) && !sgn(y-r.y);};
 bool operator !=(const Po& r)const{return sgn(x-r.x) || sgn(y-r.y);}
 Po operator +(const Po& r)const{return Po(x+r.x, y+r.y);}
 Po operator -(const Po& r)const{return Po(x-r.x, y-r.y);}
 Po operator *(DB k)const{return Po(x*k,y*k);}
 Po operator /(DB k)const{return Po(x/k,y/k);}
 DB operator *(const Po&) const;
 DB operator ^(const Po&) const;

 bool operator <(const Po &r) const{return sgn(x,r.x)<0||!sgn(x,r.x)&&sgn(y,r.y)<0;}
 Po operator -()const{return Po(-x,-y);}
 Po& operator +=(const Po &r){x+=r.x,y+=r.y;return *this;}
 Po& operator -=(const Po &r){x-=r.x,y-=r.y;return *this;}
 Po& operator *=(DB k){x*=k,y*=k;return*this;}
 Po& operator /=(DB k){x/=k,y/=k;return*this;}

 DB length_sqr()const{return sqr(x)+sqr(y);}
 DB length()const{return sqrt(length_sqr());}
 Po unit()const{return *this/length();}
 bool dgt()const{return !sgn(x)&&!sgn(y);}
 DB atan()const{return atan2(y,x);}
 void input(){RF(x,y);}

 void rotate(DB alpha, const Po& o = Po()){
 x -= o.x, y -= o.y;
 (*this) = Po(x * cos(alpha) - y * sin(alpha), y * cos(alpha) + x * sin(alpha)) + o;
 }

};

Po operator *(DB k, Po a){return a * k;}

struct Line{
 Po a, b;
 Line(DB x0=0, DB y0=0, DB x1=0, DB y1=0):a(Po(x0, y0)), b(Po(x1, y1)){}
 Line(const Po &a, const Po &b):a(a), b(b){}
 Line(const Line &l):a(l.a), b(l.b){}

 friend ostream& operator <<(ostream& out, Line p){return out << p.a << "-" << p.b;}
 Line operator +(Po x)const{return Line(a + x, b + x);}
 DB length()const{return (b-a).length();}
 bool dgt()const{return (b-a).dgt();}
 void input(){a.input(), b.input();}
 void getequation(DB, DB, DB) const;
};

struct Seg: Line{
};

#define innerProduct dot
#define scalarProduct dot
#define dotProduct dot
#define outerProduct det
#define crossProduct det

inline DB dot(const DB &x1, const DB &y1, const DB &x2, const DB &y2){return x1 * x2 + y1 * y2;}
inline DB dot(const Po &a, const Po &b){return dot(a.x, a.y, b.x, b.y);}
inline DB dot(const Po &p0, const Po &p1, const Po &p2){return dot(p1 - p0, p2 - p0);}
inline DB dot(const Po &o, const Line &l){return dot(o, l.a, l.b);}
inline DB dot(const Line &l, const Po &o){return dot(o, l.a, l.b);}
inline DB dot(const Line &l1, const Line &l2){return dot(l1.b - l1.a, l2.b - l2.a);}

inline DB det(const DB &x1, const DB &y1, const DB &x2, const DB &y2){return x1 * y2 - x2 * y1;}
inline DB det(const Po &a, const Po &b){return det(a.x, a.y, b.x, b.y);}
inline DB det(const Po &p0, const Po &p1, const Po &p2){return det(p1 - p0, p2 - p0);}
inline DB det(const Po &o, const Line &l){return det(o, l.a, l.b);}
inline DB det(const Line &l, const Po &o){return det(o, l.a, l.b);}
inline DB det(const Line &l1, const Line &l2){return det(l1.b - l1.a, l2.b - l2.a);}

DB Po::operator *(const Po &r)const{return dot(*this, r);}
DB Po::operator ^(const Po &r)const{return det(*this, r);}

void Line::getequation(DB A, DB B, DB C) const{
 A = a.y - b.y, B = b.x - a.x, C = det(a, b);
}

template<class T1, class T2> inline DB dist(const T1 &x, const T2 &y){return sqrt(dist_sqr(x, y));}
template<class T1, class T2, class T3> inline DB dist(const T1 &x, const T2 &y, const T3 &z){return sqrt(dist_sqr(x, y, z));}
template<class T1, class T2> inline int dett(const T1 &x, const T2 &y){return sgn(det(x, y));}
template<class T1, class T2> inline int dott(const T1 &x, const T2 &y){return sgn(dot(x, y));}
template<class T1, class T2, class T3> inline int dett(const T1 &x, const T2 &y, const T3 &z){return sgn(det(x, y, z));}
template<class T1, class T2, class T3> inline int dott(const T1 &x, const T2 &y, const T3 &z){return sgn(dot(x, y, z));}
template<class T1, class T2, class T3, class T4> inline int dett(const T1 &x, const T2 &y, const T3 &z, const T4 &w){return sgn(det(x, y, z, w));}
template<class T1, class T2, class T3, class T4> inline int dott(const T1 &x, const T2 &y, const T3 &z, const T4 &w){return sgn(dot(x, y, z, w));}

inline DB dist_sqr(const DB &x, const DB &y){return sqr(x) + sqr(y);}
inline DB dist_sqr(const DB &x, const DB &y, const DB &z){return sqr(x) + sqr(y) + sqr(z);}
inline DB dist_sqr(const Po &a, const Po &b){return sqr(a.x - b.x) + sqr(a.y - b.y);}
inline DB dist_sqr(const Po &p, const Line &l){Po v0 = l.b - l.a, v1 = p - l.a; return sqr(fabs(det(v0, v1))) / v0.length_sqr();}
inline DB dist_sqr(const Po &p, const Seg &l){
 Po v0 = l.b - l.a, v1 = p - l.a, v2 = p - l.b;
 if (sgn(dot(v0, v1)) * sgn(dot(v0, v2)) <= 0) return dist_sqr(p, Line(l));
 else return min(v1.length_sqr(), v2.length_sqr());
}
inline DB dist_sqr(Line l, Po p){return dist_sqr(p, l);}
inline DB dist_sqr(Seg l, Po p){return dist_sqr(p, l);}
inline DB dist_sqr(Line l1, Line l2){
 if (sgn(det(l1, l2)) != 0) return 0;
 return dist_sqr(l1.a, l2);
}
inline DB dist_sqr(Line l1, Seg l2){
 Po v0 = l1.b - l1.a, v1 = l2.a - l1.a, v2 = l2.b - l1.a; DB c1 = det(v0, v1), c2 = det(v0, v2);
 return sgn(c1) != sgn(c2) ? 0 : sqr(min(fabs(c1), fabs(c2))) / v0.length_sqr();
}

bool isIntersect(Seg l1, Seg l2){

 if (l1.a == l2.a || l1.a == l2.b || l1.b == l2.a || l1.b == l2.b) return true;

 return
 min(l1.a.x, l1.b.x) <= max(l2.a.x, l2.b.x) &&
 min(l2.a.x, l2.b.x) <= max(l1.a.x, l1.b.x) &&
 min(l1.a.y, l1.b.y) <= max(l2.a.y, l2.b.y) &&
 min(l2.a.y, l2.b.y) <= max(l1.a.y, l1.b.y) &&
 sgn( det(l1.a, l2.a, l2.b) ) * sgn( det(l1.b, l2.a, l2.b) ) <= 0 &&
 sgn( det(l2.a, l1.a, l1.b) ) * sgn( det(l2.b, l1.a, l1.b) ) <= 0;

}

inline DB dist_sqr(Seg l1, Seg l2){
 if (isIntersect(l1, l2)) return 0;
 else return min(dist_sqr(l1.a, l2), dist_sqr(l1.b, l2), dist_sqr(l2.a, l1), dist_sqr(l2.b, l1));
}

inline bool isOnSide(const Po &p, const Seg &l){
 return p == l.a || p == l.b;
}

inline bool isOnSeg(const Po &p, const Seg &l){
 return sgn(det(p, l.a, l.b)) == 0 &&
 sgn(l.a.x, p.x) * sgn(l.b.x, p.x) <= 0 && sgn(l.a.y, p.y) * sgn(l.b.y, p.y) <= 0;
}

inline bool isOnSegg(const Po &p, const Seg &l){
 return sgn(det(p, l.a, l.b)) == 0 &&
 sgn(l.a.x, p.x) * sgn(l.b.x, p.x) < 0 && sgn(l.a.y, p.y) * sgn(l.b.y, p.y) < 0;
}

inline Po intersect(const Line &l1, const Line &l2){
 return l1.a + (l1.b - l1.a) * (det(l2.a, l1.a, l2.b) / det(l2, l1));
}

// perpendicular foot
inline Po intersect(const Po & p, const Line &l){
 return intersect(Line(p, p + Po(l.a.y - l.b.y, l.b.x - l.a.x)), l);
}

inline Po rotate(Po p, DB alpha, const Po& o = Po()){
 p.x -= o.x, p.y -= o.y;
 return Po(p.x * cos(alpha) - p.y * sin(alpha), p.y * cos(alpha) + p.x * sin(alpha)) + o;
}

} using namespace CG;//}
//}

/** I/O Accelerator Interface .. **/ //{
template<class T> inline T& RD(T &x){
 //cin >> x;
 scanf("%d", &x);
 //char c; for (c = getchar(); c < '0'; c = getchar()); x = c - '0'; for (c = getchar(); '0' <= c && c <= '9'; c = getchar()) x = x * 10 + c - '0';
 //char c; c = getchar(); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';
 return x;
}

inline char* RS(char *s){
 //gets(s);
 scanf("%s", s);
 return s;
}

int Case; template<class T> inline void OT(const T &x){
 //printf("Case %d: %d\n", ++Case, x);
 printf("%.2lf\n", x);
 //printf("%d\n", x);
 //cout << x << endl;
}
//}

//}/* .................................................................................................................................. */

const int N = 100009;
Po p[N], O, E, G;
int n; DB r;

DB get_alpha(const Po& l1, const Po& l2){
 //return acos(dot(l1, l2) / (l1.length() * l2.length()));
 return asin(det(l1, l2) / (l1.length() * l2.length()));
}

DB get_theta(double alpha, double r, double l){
 return asin(sin(alpha)/r*l) - alpha;
}

void init(){
 int t1, t2, t; RD(n, t1, t2, t); REP(i, n) p[i].input();
 E -= O; REP(i, n) p[i] -= O; O = Po();
 DB alpha = -E.atan(); REP(i, n) p[i].rotate(alpha);
 E.rotate(alpha); p[n] = p[0];

 // find the center of mass .. .
 DB mass = 0; G = Po(); REP(i, n){
 DB t = p[i] ^ p[i+1]; mass += t;
 G += (p[i] + p[i+1]) * t;
 }

 G /= 3 * mass;

 // rotateion && revolution .. .
 DB revang=(t%t1)*(2*PI/t1), rotang=(t%t2)*(2*PI/t2);
 REP(i, n) p[i].rotate(rotang,G);
 Po offset = G; G.rotate(revang, E); offset = G - offset;
 REP(i, n) p[i] = p[i] + offset;
}

DB calc(){
 DB alpha = acos(r/E.x), ans = 2*r*alpha;
 if(sgn(dot(E,O,G)) < 0) return ans;
 alpha = PI/2 - alpha;

 Po lp = p[0], rp = p[0]; FOR(i, 1, n){
 if(det(lp, p[i]) < 0) lp = p[i];
 else if(det(rp, p[i]) > 0) rp = p[i];
 }

 DB la = max(-alpha, get_alpha(E, lp)), ra = min(alpha, get_alpha(E, rp));
 if(ra < la) return ans; // ?

 ans -= r * (get_theta(ra,r,E.x)-get_theta(la,r,E.x));
 return ans;
}

int main(){

#ifndef ONLINE_JUDGE
 freopen("in.txt", "r", stdin);
 //freopen("out.txt", "w", stdout);
#endif

 while(~scanf("%lf%lf%lf%lf%lf",&O.x,&O.y,&E.x,&E.y,&r)){
 init(); OT(calc());
 }
}

  1. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的