Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 1A

Posted by KatrineYang at 2016-09-04 01:58:16 on Problem 1265 and last updated at 2016-09-04 01:58:21
```#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;

const double PI = 3.1415926535;

int ABS(int a){
if(a < 0) return -a;
return a;
}

int GCD(int a, int b){
a = ABS(a), b = ABS(b);
if(a == 0) return b;
if(b == 0) return a;
if(a >= b) return GCD(a%b, b);
return GCD(b%a, a);
}

struct pt{
int x,y;
pt *prev, *next;
}pts[233];

double mianji(pt &p1, pt &p2, pt &p3){
return abs(0.5 * (p1.x*p2.y+p2.x*p3.y+p3.x*p1.y-p1.y*p2.x-p2.y*p3.x-p3.y*p1.x));
}

double angle(pt &p1, pt &p2){
double a = atan2(p2.y-p1.y+0.0, p2.x-p1.x+0.0);
if(a >= 0) return a;
return a + 2*PI;
}

double angle(pt &p1, pt &p2, pt &p3){
double a1 = angle(p2, p1), a2 = angle(p2, p3);
if(a1 - a2 >= 0) return a1-a2;
return a1 - a2 + 2*PI;
}

int sign(pt &p1, pt &p2, pt &p3){
int get = p1.x*p2.y + p2.x*p3.y + p3.x*p1.y - p1.y*p2.x - p2.y*p3.x - p3.y*p1.x;
if(get > 0) return 1;
else if(get < 0)return -1;
else return 0;
}

bool neimian(pt &nd, pt &p1, pt &p2, pt &p3){
int sign1 = sign(nd, p1, p2), sign2 = sign(nd, p2, p3), sign3 = sign(nd, p3, p1);
bool z = 0, f = 0;
if(sign1 == 1) z = 1;
if(sign1 == -1) f = 1;
if(sign2 == 1) z = 1;
if(sign2 == -1) f = 1;
if(sign3 == 1) z = 1;
if(sign3 == -1) f = 1;
return !(z && f);
}

int main() {
int T;
scanf("%d", &T);
for(int ii = 1; ii <= T; ii++){
printf("Scenario #%d:\n", ii);
int num;
scanf("%d", &num);
//int x[233], y[233];
//x[0] = y[0] = 0;
int bj = num;
int curX = 0, curY = 0;
for(int i = 0; i < num; i++){
//x[i] = curX, y[i] = curY;
pts[i].x = curX, pts[i].y = curY;
pts[i].next = &pts[(i+1)%num], pts[i].prev = &pts[(i+num-1)%num];
int tmpX, tmpY;
scanf("%d%d", &tmpX, &tmpY);
bj += GCD(tmpX, tmpY)-1;
curX += tmpX, curY += tmpY;
}
double yjddmj = 0.0;
pt *curP = &pts[0];
int sygs = num;
while(1){
//cout << sygs << endl;
int cnt = 0;
while(1){
//cout << cnt << endl;
if(angle(*(curP->prev), *curP, *(curP->next)) > PI-1e-8){
bool ky = 1;
pt *temp = curP->next->next;
while(temp != curP->prev){
//cout << (temp - pts) << endl;
if(neimian(*temp, *(curP->prev), *(curP), *(curP->next))){
ky = 0;
break;
}
temp = temp->next;
}
if(ky) break;
}
cnt ++;
curP = curP->next;
if(cnt > sygs) goto done;
}
yjddmj += mianji(*(curP->prev), *curP, *(curP->next));
sygs --;
curP->next->prev = curP->prev;
curP->prev->next = curP->next;
curP = curP->next;
}
done:
double mj = 0;
pt *curPP = curP->next;
while(curPP->next != curP){
//cout << 1 << endl;
mj += mianji(*curP, *curPP, *(curPP->next));
curPP = curPP->next;
}
mj -= yjddmj;
int nd = (int)(mj + 1 - 0.5 * bj);
printf("%d %d %.1lf\n\n", nd, bj, mj);
}
return 0;
}
```

Followed by: