- 1#include 2#include < set > 3#include 4#include 5#include 6#include 7#include < string > 8#include 9#include 10#include 11#include 12#include 13#include 14#include 15 using namespace std;
- 16#define rep(i, a, n) for (int i = a; i 17#define per(i, a, n) for (int i = n - 1; i >= a; i--) 18#define all(x)(x).begin(), (x).end() 19#define pb push_back 20#define mp make_pair 21#define lson l, m, rt << 1 22#define rson m + 1, r, rt << 1 | 1 23 typedef long long ll; 24 typedef vector < int > VI; 25 typedef pair < int, int > PII; 26 const ll MOD = 1e9 + 7; 27 const int INF = 0x3f3f3f3f; 28 const int MAXN = 2e4 + 7; 29 // head
- 30 31 const double eps = 1e-8; 32 int cmp(double x) {
- 33
- if (fabs(x) < eps) return 0;
- 34
- if (x > 0) return 1;
- 35
- return - 1;
- 36
- }
- 37 38 const double pi = acos( - 1); 39 inline double sqr(double x) {
- 40
- return x * x;
- 41
- }
- 42 struct point {
- 43 double x,
- y;
- 44 point() {}
- 45 point(double a, double b) : x(a),
- y(b) {}
- 46 void input() {
- 47 scanf("%lf%lf", &x, &y);
- 48
- }
- 49 friend point operator + (const point & a, const point & b) {
- 50
- return point(a.x + b.x, a.y + b.y);
- 51
- }
- 52 friend point operator - (const point & a, const point & b) {
- 53
- return point(a.x - b.x, a.y - b.y);
- 54
- }
- 55 friend point operator * (const double & a, const point & b) {
- 56
- return point(a * b.x, a * b.y);
- 57
- }
- 58 friend point operator / (const point & a, const double & b) {
- 59
- return point(a.x / b, a.y / b);
- 60
- }
- 61 double norm() {
- 62
- return sqrt(sqr(x) + sqr(y));
- 63
- }
- 64
- }; 65 double det(point a, point b) {
- 66
- return a.x * b.y - a.y * b.x;
- 67
- }
- 68 double dot(point a, point b) {
- 69
- return a.x * b.x + a.y * b.y;
- 70
- }
- 71 double dist(point a, point b) {
- 72
- return (a - b).norm();
- 73
- }
- 74 75 struct line {
- 76 point a,
- b;
- 77 line() {}
- 78 line(point x, point y) : a(x),
- b(y) {}
- 79
- }; 80 double dis_point_segment(point p, point s, point t) {
- 81
- if (cmp(dot(p - s, t - s)) < 0) return (p - s).norm();
- 82
- if (cmp(dot(p - t, s - t)) < 0) return (p - t).norm();
- 83
- return fabs(det(s - p, t - p) / dist(s, t));
- 84
- }
- 85 bool point_on_segment(point p, point s, point t) {
- 86
- return cmp(det(p - s, t - s)) == 0 && cmp(dot(p - s, p - t)) <= 0;
- 87
- }
- 88 bool parallel(line a, line b) {
- 89
- return ! cmp(det(a.a - a.b, b.a - b.b));
- 90
- }
- 91 bool line_make_point(line a, line b, point & res) {
- 92
- if (parallel(a, b)) return false;
- 93 double s1 = det(a.a - b.a, b.b - b.a);
- 94 double s2 = det(a.b - b.a, b.b - b.a);
- 95 res = (s1 * a.b - s2 * a.a) / (s1 - s2);
- 96
- return true;
- 97
- }
- 98 99 struct polygon {
- 100 int n;
- 101 point a[MAXN];
- 102 double area() {
- 103 double sum = 0;
- 104 a[n] = a[0];
- 105 rep(i, 0, n) sum += det(a[i], a[i + 1]);
- 106
- return sum / 2;
- 107
- }
- 108 point MassCenter() {
- 109 point ans = point(0, 0);
- 110
- if (cmp(area()) == 0) return ans;
- 111 a[n] = a[0];
- 112 rep(i, 0, n) ans = ans + det(a[i + 1], a[i]) * (a[i] + a[i + 1]);
- 113
- return ans / area() / 6;
- 114
- }
- 115 int gcd(int a, int b) {
- 116
- return b == 0 ? a: gcd(b, a % b);
- 117
- }
- 118 int Border_Int_Point_Num() {
- 119 int num = 0;
- 120 a[n] = a[0];
- 121 rep(i, 0, n) num += gcd(abs(int(a[i + 1].x - a[i].x)), 122 abs(int(a[i + 1].y - a[i].y)));
- 123
- return num;
- 124
- }
- 125 int Inside_Int_Point_Num() {
- 126
- return int(area()) + 1 - Border_Int_Point_Num() / 2;
- 127
- }
- 128
- }; 129 130 int n; 131 polygon p; 132 133 int main() {
- 134 int T;
- 135 cin >> T;
- 136 rep(cas, 1, T + 1) {
- 137 cin >> n;
- 138 p.n = n;
- 139 rep(i, 0, n) scanf("%lf%lf", &p.a[i].x, &p.a[i].y);
- 140 rep(i, 1, n) p.a[i] = p.a[i] + p.a[i - 1];
- 141 int a = p.Inside_Int_Point_Num();
- 142 int b = p.Border_Int_Point_Num();
- 143 double c = p.area();
- 144 printf("Scenario #%d:\n%d %d %.1f\n\n", cas, a, b, c);
- 145
- }
- 146
- return 0;
- 147
- }
来源: http://www.bubuko.com/infodetail-2031636.html