Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator