다각형의 넓이 구하기

source.cpp

#define TIMETEST 0

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>

#if (TIMETEST)
#include <chrono>//for time check
#endif

using namespace std;

struct Vec2{
	double x;
	double y;
	Vec2()
	{
		x=0.0;
		y=0.0;
	}
	Vec2(double _x,double _y)
	{
		x=_x;
		y=_y;
	}
};

vector<Vec2> inPosArr;
vector<Vec2> resPosArr;

bool checkLine(Vec2 a, Vec2 b, Vec2 p)
{
	double base = (b.y-a.y)/(b.x-a.x)*(p.x-a.x) + a.y;

	if(base <= p.y)//up
		return true;
	else//down
		return false;
}

bool compareVec2(const Vec2 &a, const Vec2 &b)
{
	if(a.x==b.x)
		return a.y > b.y;
	else
		return a.x < b.x;
}

int main()
{
#if (TIMETEST)
	std::chrono::duration<double> sec;
#endif
	std::ios::sync_with_stdio(false);
#if (TIMETEST)
	std::chrono::system_clock::time_point start = std::chrono::system_clock::now();
#endif
	int n = 0;
	cin>>n;//test case <=100
	for(int i=0;i<n;i++)
	{
		vector<Vec2> downPosArr;
		vector<Vec2> upPosArr;
		Vec2 posA(0,0);
		Vec2 posB(0,0);

		int dotCount=0;
		cin>>dotCount;
		for(int j=0;j<dotCount;j++)
		{
			int x,y;
			cin>>x>>y;
			inPosArr.push_back(Vec2(x,y));
		}

		//find point A, B 
		posA = inPosArr[0];
		posB = inPosArr[1];

		for(int j=0;j<dotCount;j++)
		{
			if(posA.x > inPosArr[j].x)
			{
				posA = inPosArr[j];
			}
			else if(posA.x==inPosArr[j].x)
			{
				posA.y < inPosArr[j].y ? posA=inPosArr[j] : posA=posA;
			}
			if(posB.x < inPosArr[j].x)
			{
				posB = inPosArr[j];
			}
			else if(posB.x==inPosArr[j].x)
			{
				posB.y > inPosArr[j].y ? posB=inPosArr[j] : posB=posB;
			}
			
		}

		//make upArr, downArr
		for(int j=0;j<dotCount;j++)
		{
			if(checkLine(posA,posB,inPosArr[j]))//up
				upPosArr.push_back(inPosArr[j]);
			else//down
				downPosArr.push_back(inPosArr[j]);
		}

		sort(upPosArr.begin(),upPosArr.end(),compareVec2);
		sort(downPosArr.begin(),downPosArr.end(),compareVec2);

		resPosArr.insert(resPosArr.end(),upPosArr.begin(),upPosArr.end());
		resPosArr.insert(resPosArr.end(),downPosArr.rbegin(),downPosArr.rend());

		int k=0;
		long double area=0.0;

		for(int j=0; j<dotCount; j++)
		{
			k = (j+1)%dotCount;

			Vec2 vec1 = resPosArr[j];
			Vec2 vec2 = resPosArr[k];

			double x1 = vec1.x;
			double y1 = vec1.y;
			double x2 = vec2.x;
			double y2 = vec2.y;

			area = area + x1*y2;
			area = area - x2*y1;
		}
		area /=2.0;
		area = fabs(area);
		cout<<(long long int)(area*10000)<<endl;

		resPosArr.clear();
		inPosArr.clear();
		downPosArr.clear();
		upPosArr.clear();
	}
#if (TIMETEST)
	sec = std::chrono::system_clock::now() - start;
	cout<<"time : "<<sec.count()<<"secs"<<endl;
#endif
	return 0;
}